As of May 31, 2023, we have updated our Code of Conduct.

# Questions tagged [sets]

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

74 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
1k views

### Alternative to Bloom filter for extreme parameters

A Bloom filter is a space-efficient probabilistic data structure to perform membership-tests on a set (see Wikipedia's page for a definition; I use the same notations below). I am interested in a ...
166 views

### Overlap Maximization problem

Here's the problem: I have a collection of collections, $C$, where each $c\in C$ is a collection of sets $X\subset U$. Denote $c_i$ as the i-th $X$ in $c$. Informally, I want to map all the sets in ...
39 views

57 views

### Map-like data structure with subsets as keys

I am looking for a map-like data structure with the following properties: it uses subsets of some set S as keys. The size of S is potentially unbounded, but does not change during the runtime the ...
148 views

### Changing a family of sets to become laminar

A family of sets $F = \{S_1, \dots, S_n\}$ on the ground set $S$ is laminar, if for every $1\leq i < j \leq n$, either $S_i \subsetneq S_j$ or $S_j \subsetneq S_i$ or $S_i \cap S_j = \varnothing$ ...
39 views

### Components of subset partial order

Given a collection C of sets, there are a number of proposed algorithms for building the subset partial order, e.g. this paper. But is there any work on algorithms ...
321 views

142 views

### physical significance of membership function greater than one

In fuzzy logic, when we associate an element with a set, we usually do it in terms of membership grade which suggests the "belonging" of this element to the set. Membership grade value 0 means that ...
63 views

### Ordered set transformation data structure

Assume an ordered set $M = \{\tau_1, \tau_2, ..., \tau_n\}$ and a subset $S = \{\tau_k,\tau_l,...,\tau_m\}\subset M$ where $1\leq k,l,m \leq n$. All the items of $S$ are randomly ordered. The task is ...
714 views

### Efficient algorithm to approximate membership in a set of strings

I devised an algorithm / data structure and I would like to ask whether it already exists. The problem statement is: after having added some number of strings to the set, determine whether a given ...
77 views

### Tradoff between space and false positive rate when using bloom filters

Bloom Filters have false positive rate of $\epsilon = 2^{-k}$ with a data structure of size $m = n\log (\frac{1}{\epsilon})\ln 2$. Suppose you fix the number of hash functions at $k \le 3$. What is ...
129 views

### Message protocol to probabilistically infer missing object from Union of two subsets of a larger set

This was a challenge problem I read some time ago and just remembered it: Say you have two people, $A$ and $B$, collect objects distinctly labeled $1,...,n$. They will each separately collect sets ...
60 views

### What is the time complexity of removing among $N$ sets of size at most $n$ the sets which are subsets of another set?

A naïve solution would be to first sort all sets, taking time $O(N n \log n)$. Then, for every possible pair of sets, check if one is a subset of the other, and if applicable remove the subset. This ...
124 views

### How to speed up finding a subset of a given set?

Is there a data indexing technique that speeds up finding subsets of a given set in a collection, or do I always have to scan all of the data? For example, let's say that I have a collection of sets: ...
1 vote
19 views

### Randomly Split a Bar Into Beats

So I'm writing a software that generates random MIDI tracks based on a given mode, tonal etc. As for now the randomisation works on tones building sequences of equal duration. What I'd like to do is ...
1 vote
46 views

### Prove that a dominating set has minimum cardinality in a "unit interval graph"

I am given the definition of a unit interval graph, e.g. $G = (V, E)$ such that $\forall v \in V$ there is a weight $x_v \in \mathbb{R}$ and nodes $u, w$ has an edge iff $|x_u - x_w| < 1$. I am ...
1 vote
62 views

### Find sets which are subsets of the given search set?

The problem is the following: You are given a collection( set, list, whatever ) C of sets, and you are given a search set S. We want to find among all sets in C the ones which are subsets of S. Hence, ...
1 vote
49 views

### Is there a distributed streaming algorithm to verify set cover?

I have $k$ sets of similar sizes, that cover a universe $U$. e.g. for $k=3$ and $U = \{1, 2, 3, 4, 5, 6\}$: $S_0 = \{1, 2, 4\}$ $S_1 = \{2, 3, 4\}$ $S_2 = \{4, 5, 6\}$ I have another larger set $C$ ...
1 vote
35 views

### Selecting sets that maximise the cardinality of the union minus the cardinality of the difference

I have a sparse $60000\times10000$ matrix where each element is either a $1$ or $0$ as follows. M=\begin{bmatrix}1 & 0 & 1 & \cdots & 1 \\1 & 1 & 0 & \cdots & 1 \\0 &...
1 vote
21 views

### Streaming maximum pair matching with limited memory

I am trying to find as many pairs of elements as possible from two distinct data streams, while being constrained by the number of elements I can hold in memory at any given time. Once a pair of ...
1 vote
67 views

### Disjoint groups using maximum matching

In the 3-Path Packing problem, we are given an undirected graph $G$ and a parameter $k \in \mathbb{N} \cup \{0\}$. We need to answer Yes/No if there exists a collection of $k$ vertex disjoint paths on ...
1 vote
41 views

### Minimal number of unions of sets such that no union has more than N elements

I have some sets, and can combine them by taking their union. I can take unions of the unions, too. I want to take unions until the total number of sets is as small as possible, with one caveat: that ...
1 vote
52 views

### Clustering sets by set difference

Suppose you have $n$ nonequal sets $S_1, \ldots, S_n$ and some constant $0 \le k < n$. The goal of set clustering is to find a partition of the set $\mathbf{S} = \{S_1, \ldots, S_n\}$ such that the ...
1 vote
43 views

### Set data structure for data too large to fit into memory

I'm trying to solve the following exercise: Given N data items and memory that can hold M/B blocks of size B. Describe a data structure that needs at most N/B blocks of external memory and allows ...
1 vote
43 views

### Optimally find one of the total orderings for a poset based on some metadata about the elements

Given a finite, partially ordered set with the following two properties: Every element in the set has one of two types: "A" or "B". The type does not define the total ordering of the set and is ...
1 vote
34 views

### Algorithm for finding the set of systems of distinct representatives

Given a collection of finite sets, is there an algorithm for finding the set (unordered) of all systems of distinct representatives for the collection? Example: S: {{1, 2}, {1, 2, 3}} Unordered ...
1 vote
255 views

### Data structure for overlapping sets

Is there a good data structure for storing overlapping sets? Consider having multiple sets which can overlap in various ways and would like to store them in the memory and access efficient way. ...
1 vote
55 views

### The maximum number of uniquely intersected elements from the all possible intersection scenarios among the sets in a two-column matrix

Let us define a $n \times 2$ matrix M consisting of integer sets, such that the first column consists of the so-called intersecting sets, and the second column ...
1 vote
86 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 ...
1 vote
73 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 ...
1 vote
187 views

### Representing multisets by a bit vector

What would be the most space-efficient way to represent a multiset (a set that can contain duplicates) using a (static) bit string (bit vector, bit array, etc.)? All of the elements in the multiset ...
1 vote
723 views

### Complexity of set oprations in algorithm

I am designing a graph algorithm. Some steps of the algorithm, are set operations (union, difference, intersection, set-membership). Can I assume them as $~ \mathcal{O}(1)$ operations? Have someone ...
1 vote
My attempt to solve this: If $\mathcal{A}$ is an arbitrary infinite recursive set then the members of $\mathcal{A}$ can be ordered in ascending order. We can do bijection between $\mathcal{N}$ and \$\...