# Questions tagged [sets]

Questions about finite and infinite sets and multisets, related data structures and concepts.

316 questions
Filter by
Sorted by
Tagged with
186 views

### Finding longest subset arithmetic progression with given difference

Given a list of distinct positive integers, I am trying to find the largest subset that forms an arithmetic sequence with a given difference D. For example, given D = 5, with the set of numbers 1, 5, ...
61 views

### How do you compute the Pareto Front of a set?

I need to decide which solution is the best design, in order to do that I need to compare them. Lower energy used and lower weight is better. My initial idea was to order both the fields best to worst ...
43 views

### Complexity of set partition generation while equivalence relation is given

Given a binary equivalence relation, R on a set A, Let P be the resulting partition. I want to generate the partition means each subset in the partition. What would be the fastest algorithm for this ...
129 views

60 views

### Find a partition of multiset of binomial coefficients with constriants

Given the multiset $S$ where the elements are defined by the binomial coefficient ${n \choose k}$ where $n \in \mathbb{N}$ and $0\leq k \leq n$ find the partition $P$ of $S$ such that the sum of ...
46 views

### Can You List the Names of Some Algorithms For Determining the Intersection of Two Context Free Grammars?

Suppose we have two sets of strings XS and YS such that set XS is described by grammar GX and YS is described by grammar GY. We want an algorithm which accepts GX and Gy as inputs. The algorithm will ...
47 views

### Find four sets where each element from those four appears in at least two of those four sets

I have a list of sorted arrays ("sets") of integers $A_1..A_n$ where each element is unique w.r.t. the other elements in the same array: $A_i = \{x_{i,1}..x_{i,c_i}\}$ $x_{i,p} < x_{i,p+1}$ $A_i$ ...
82 views

### Given a set $A$ of sets find a minimal set $B$ of pair-wise disjoint sets such that each set in $A$ can be expressed as a union of sets in $B$

I recently thought of the following problem: Given a set $A$ of sets find a minimal set $B$ of pair-wise disjoint sets such that each set in $A$ can be expressed as a union of sets in $B$. For ...
498 views

### set cover where only certain special subsets are allowed

I am trying to solve a problem which turns out to be a form of the set cover problem. I've implemented the greedy Set cover approximation algorithm for set cover, but it turns out to not be accurate ...
36 views

### Is a set $B = \{y, \exists x \in A, f(x)=y\}$ recursive if A is a recursive set and f is a $N->N$ total computable function?

Obviously, B would be recursive if for every TCF f, there was an inverse fuction that would return all possible values, as we could just take these and then check if any of them is in A. However I ...
93 views

### Minimal set of subintervals that 'covers' any subinterval in K subintervals

I have a big interval $I = [a, b]$ of size n. I want an asymptotically minimal set of subintervals of $I$ (let's call it $S$) one can use to construct any subinterval of $I$, by concatenating at most ...
79 views

### Algorithm / data structure to filter documents by number of missing words

Is there a data structure or an algorithm or a combination of both to allow me to filter a set of documents based on the number of missing words (compared to another list)? Problem Definition We ...
124 views

### Parser theory: How to systematically compute FOLLOW sets?

Forgive me for my ignorance as I am self-teaching myself some of this theory... I am having some trouble understanding how to systematically/algorithmically compute FOLLOW sets, given that I have ...
51 views

### PL: What solves the type isomorphism $X \cong (X \rightarrow \mathbf{2})$?

In Practical Foundations for Programming Languages, on page 138 (page 156 of the pdf), it says: Requiring solutions to all type equations may seem suspicious, because we know by Cantor’s Theorem ...
338 views

### Prove/disprove that the class of decidable (resp. partially decidable) languages is closed under symmetric difference

Prove/disprove that the class of decidable (resp. partially decidable) languages is closed under symmetric difference. A symmetric difference of sets A and B is the set (A \ B) ∪ (B \ A). I know that ...
60 views

### Algorithm for Minimum Subset Needed to Satisfy all Constraints

I was wondering what is the most efficient algorithm to solve something like the following: You have $P$ people. You have $T$ tasks, each of which is a set of sets that represent all of the possible ...
302 views

146 views

### What is the most efficient algorithm for creating a list of unique values from a list of pairs of value?

Background I have a list of 50 million $A-A_i$ pairs, where $i>1$, and $A$ and $A_i$ are some text. I need to extract the $A$ values from the list, so I get a new list of unique $A$ values.:  \...
98 views

2k views

### Given n numbers How to find out a set of numbers whose sum equal to a certain given number

I am given an list of numbers and A number-s. I need to find out the collection(s) of numbers from the list of numbers whose sum corresponds to the given number s. ...
38 views

### complexity of outputting the union of a collection of subsets of a set

This question concerns the time complexity of outputting the unions of subsets of a given set. Given $m$ subsets of an $k$-element set, can the union of those sets be computed in linear time with ...
190 views

### Print all subsets of a set ($a$) of $n$ positive integers, such that the product of their elements equals $p$

I have the following problem: Given a set a of n positive integers, write a backtracking C function that prints out all the subsets of a such that the product of their elements is p. Use an array ...
We have given a multiset of $N$ integer, both positive or negative. Consider all $2^N$ subsets, sorted by their sum (the empty subset has sum 0). We want an algorithm that outputs only the first $K$ ...