# Questions tagged [sets]

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

284 questions
Filter by
Sorted by
Tagged with
14 views

### Given a set of sets, what is the largest common intersection between them?

Given a set of sets: $S = \{~\{1, 2, 3\}, \{2, 3, 4\}, \{1, 3, 4\}~\}$, I would like to find the largest common subset of $S$. If $S$ does not have a subset across all elements of $S$, I would like to ...
42 views

### Largest number of unique values in sets

Let's say I have 100 sets of values, and each set contains roughly 100,000 values. From these sets, I want to find the 10 sets that collectively have the largest number of unique values. The brute ...
19 views

### Proving set of finite languages vs all languages over finite alphabet to be countable / uncountable

I came across following facts: Set of finite languages over a finite alphabet is countable. Set of languages over finite alphabet is uncountable. I believe proof of this will be similar to ...
36 views

### Is it possible to determine if 2 arrays contain the same elements (ignoring duplicates) in faster than O(n log n) time?

So given 2 arrays of equal length, is it possible to determine whether the 2 arrays contain the same elements (ignoring duplicates and where those elements have a total order relation) with time ...
14 views

### How to find number of combinations of choosing one from k subsets

Consider we have set S: S = {1,2,3,4,5,6} and 3 (say k) subsets of S: S_1 = {1,2,3} S_2 = {2,3,4,5} S_3 = {1,3,6} What is the total number of cases choosing one element from each subsets? Same ...
30 views

### largest bitwise-or subset with a maximum number of on bits?

Suppose I have the following set of bit sets: ...
50 views

### Hitting Set Problem with non-minimal Greedy Algorithm

The Hitting Set Problem is defined as having a universal set $\mathfrak{U}$, and nonempty sets $S_i \subseteq \mathfrak{U}$ for $1 \leq i \leq n$, and finding a set $\mathcal{H} \subset \mathfrak{U}$ ...
29 views

### A problem on sets

Given a collection C of sets, with union U, find a choice function which chooses a distinct element from each of the sets such that the union of the singleton distinct elements is U. As an example, ...
39 views

### Efficient data structure for matching 3D lines

I'd like to Store a set of many infinite undirected 3D lines. Make lookups against this set - i.e. given an arbitrary line, ask "Does the set contain a line coincident with this one?" The incidence-...
71 views

### Set of maximum overlaps

Assume I have a list of $N$ surfaces $\{S_i\}, i \in [1,N]$ which may or may not overlap. I also have a boolean function $F(S_{i_1},\dots,S_{i_k})$ (with $1 \le k \le N$) which tests whether all ...
48 views

### How to partition disagreeable people into compatible groups

We have a number of people that must be partitioned into groups, but there may be people that dislike other individuals. Partition the people into the minimum number of groups such that no person is ...
53 views

### How can $A \cup B$ be decidable if $B$ is undecidable?

My assignment says: "Determine if the following statement is correct: If $A$ and $A \cup B$ are decidable, then $B$ is decidable." The solution says: "Incorrect. If $B = H_0 \subseteq \{0,1\}^*$ ...
38 views

### Proof of sparsification lemma: What exactly does the $\pi$ operator do?

In their proof of the sparsification lemma, Impagliazzo et. al describe the following operator $\pi$: For a familiy of sets $\mathcal{F}$, let $\pi(\mathcal{F}) \subseteq \mathcal{F}$ be the family ...
39 views

### Disjoint Set Connected Components With Weighted Graph

I have been trying to solve this HackerRank problem (link). The basic premise of this problem is that there is a tree with undirected, but weighted, edges. The cost of a path in this tree is taken ...
77 views

### Lambda Calculus as a branch of set theory

This answer to a question about whether C is the mother of all languages contained an interesting tidbit that I am curious about: The functional paradigm, for example, was developed mathematically (...
23 views

### For a collection $S$ of weighted sets $S_i$, find those $k$ elements that maximise the sum of weights of all sets $S_i$ covered by them

I have a collection $S$ of sets $S_i$. Each $S_i$ has a weight given by how many times this set was observed in some data. I now want to find the $k$ elements that maximize the cumulative weight of ...
109 views

### Suggest a Data Structure To Manage 2 Sets

I was given the following problem which really baffled me, and I would like some guidance in solving it. I want to make a data-structure which represents two sets $A,B\subseteq \mathbb{R}$, so that I ...
65 views

### Fast hash function for set equality

I'm searching an hash function for integer set equality that must be fast. It must support update (adding an element already in the set must not change the hash) and union. MinHash has these 2 ...
120 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, ...
50 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 ...
36 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 ...
73 views

51 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 ...
43 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 ...
45 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$ ...
73 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 ...
373 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 ...
29 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 ...
81 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 ...
61 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 ...