Questions tagged [sets]

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

80 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
11 votes
0 answers
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 ...
doc's user avatar
  • 391
7 votes
0 answers
170 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 ...
torquestomp's user avatar
6 votes
0 answers
43 views

How to find the minimum number of elements to distinguish several given sets?

Given $n$ distinct sets $S_1, S_2, \cdots, S_n$, how to find a set $X$ such that $X \cap S_1, X \cap S_2, \cdots, X \cap S_n$ are still distinct, and the size of $X$ is minimum? For example, given $\{...
user avatar
6 votes
0 answers
1k views

Time complexity of obtaining the support set of an unsorted sequence?

Consider a sequence $s$ of $n$ integers (let's ignore the specifics of their representation and just suppose we can read, write and compare them in O(1) time with arbitrary positions). What's known ...
einpoklum's user avatar
  • 965
4 votes
0 answers
37 views

Cardinalities in set coverings

Let $I$ be a set of items; $C \subseteq \mathcal{P}(I)$ be a set of subsets of $I$, where $\mathcal{P}(I)$ stands for the power set of $I$; And $C(i) = \{ c \in C \mid i \in c \}$ be the set of sets, ...
Matheus Diógenes Andrade's user avatar
4 votes
0 answers
82 views

Finding all sets which are not subsets of other sets

I have a set of sets, for example { {1, 2, 3}, {1, 2}, {2}, {2, 4} } I want to find all sets which are not subsets of another set. For example, ...
Daniel M.'s user avatar
  • 141
4 votes
0 answers
145 views

Sequence where every subset exists as some contiguous subsequence

Given a set (i.e., a collection of distinct elements), how would you find a minimal sequence where every subset of that set can be found as the elements in some contiguous subsequences? The order of ...
magnetlion's user avatar
3 votes
0 answers
158 views

Maximum set cover with non-overlap

Let the universe be the set $U$ and a set of subsets $S$ be such that $\cup_{s \in S} s = U$. I am interested in computing the longest sequence of sets $s_1, ..., s_k$ such that: $s_i \in S$ $\forall ...
in_question's user avatar
3 votes
0 answers
99 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 ...
Minop's user avatar
  • 131
3 votes
0 answers
152 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$ ...
Dandelion's user avatar
  • 287
3 votes
0 answers
44 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 ...
Radio Controlled's user avatar
3 votes
0 answers
325 views

Algorithm for minimum number of partitions to transform list of sets into Laminar Set Family

I have a list of sets $L$. I want to partition the sets in $L$ to produce a new list $L'$ that is a Laminar Set Family Concretely: For any $L'_i, L'_j \in L'$ if $L'_i \not\subseteq L'_j$ and $L'_j ...
Eli Bixby's user avatar
  • 141
3 votes
0 answers
133 views

effective, efficient algorithms on antichains

In a partially ordered set L, an antichain is a subset A of L such that no two elements of A are comparable. Antichains are commonly used to represent upward-closed subsets of L, that is, sets S such ...
David Monniaux's user avatar
2 votes
1 answer
59 views

"Consecutive statements" in Static control Part(SCoP)

Context: I was reading a research paper related to polyhedral representation(citation given in last). Got confused while trying to understand the notation by implementing them with example code. Paper ...
F.C. Akhi's user avatar
  • 123
2 votes
0 answers
110 views

SCoP, Iteration Domain in Polyhedral Optimization and use of Presburger arithmetic

Context: While exploring the fundamentals of polyhedral optimization and attempting to explore a connection from the input Static Control Part (SCoP) to the iteration domain from birds eye view, I am ...
F.C. Akhi's user avatar
  • 123
2 votes
0 answers
24 views

Windowed LogLog/HyperLogLog algorithm to get a count of the cardinality of the set of the last $k$ elements?

LogLog/HyperLogLog provides a great way for estimating the cardinality of the set of $n$ objects. At its simplest, you hash all $n$ objects into binary strings, find the largest number of leading 0's $...
chausies's user avatar
  • 532
2 votes
1 answer
85 views

Algorithm to find intersection between collection of sets

I have two dataframes representing products two distributors sell. They look like this: df1 for distributor 1. ...
nepee's user avatar
  • 280
2 votes
0 answers
45 views

Lowest total cardinality mutually exclusive construction of a superset

Let there be $N$ sequences containing at least one set each. Each set has at least one element each. Select exactly one set from each sequence. The selection within each sequence is mutually exclusive....
Reinderien's user avatar
2 votes
0 answers
159 views

Algorithm to find largest intersection of sets

This is a cross-posting from here, on the mathematics Stack Exchange. I thought this might be a more appropriate venue. The problem is this: I have a list of sets $$S_1, S_2,... S_N$$ where each set ...
Dan Goldwater's user avatar
2 votes
0 answers
51 views

Online algorithm for compressing multiple SETS?

Algorithms like LZW and others compress data sequences. What I'm looking is an algorithm that compress multiple Sets. if possible online algorithm. For example : ...
sten's user avatar
  • 139
2 votes
1 answer
78 views

Efficient Implementation of Boolean Lattice-Esque Operation

Let $X = \{1,2,\dots n\}$, and $Y_i= \{T \in \mathcal{P}(X): |T| \le i\}$. I am interested in "avoidance sets" $A \subset Y_n$. We say a subset $S \subset X$ is valid with respect to an ...
Zach Hunter's user avatar
2 votes
0 answers
156 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 ...
Valentin Hirschi's user avatar
2 votes
0 answers
52 views

Abstract Data Type

I have been studying data structures. In that I have come across topics like Array being defined as Power set of cross product of set of objects and set of natural number and list being defined as ...
Avanish Singh's user avatar
2 votes
0 answers
470 views

hash-table subsets

Having trouble figuring this out. If I have 2 sets of integers how would I use a hash table to test if set A is a subset of set B (in pseudocode). I think I understand that basically I would need to ...
Hosep's user avatar
  • 51
2 votes
0 answers
131 views

Minimum overlap partitioning

We are given $N$ sets of $M$ non-unique elements each. The amount of overlap (computed as the element count in the set intersection) between the elements of these sets is stored in a $N \times N$ ...
George's user avatar
  • 121
2 votes
0 answers
64 views

Smallest set non-disjoint with other given sets

Given a number of sets, what is the best algorithm to calculate the smallest set S such that S is not disjoint with any of the given sets?
tmwilliamlin168's user avatar
2 votes
0 answers
75 views

Finding subsets in a large collection of sets

Given a large collection $\mathcal{X} = \{X_1, X_2, \dots, X_n\}$, where each $X_i$ is a set of integers, what's a fast algorithm to identify all pairs $(i,j)$ with $i \ne j$ such that $X_i \subseteq ...
David Zhang's user avatar
2 votes
0 answers
159 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 ...
Upendra01's user avatar
  • 149
2 votes
0 answers
64 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 ...
John L. Jegutanis's user avatar
2 votes
0 answers
722 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 ...
univise's user avatar
  • 121
2 votes
0 answers
78 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 ...
Kelsey's user avatar
  • 109
2 votes
0 answers
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 ...
Four_FUN's user avatar
  • 125
2 votes
1 answer
77 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 ...
J. Schmidt's user avatar
2 votes
1 answer
145 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: ...
Bartosz Mikulski's user avatar
1 vote
0 answers
21 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 ...
Carlo Moretti's user avatar
1 vote
1 answer
75 views

Logical Consequence - Equivalent Assertions

I have the following slide in my notes and I'm having trouble understanding how the three assertions are equivalent. I understand to a degree how the 2nd and 3rd assertions are equivalent, but the ...
A. Boy's user avatar
  • 11
1 vote
0 answers
58 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 ...
NiRvanA's user avatar
  • 159
1 vote
0 answers
82 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, ...
Vladimir's user avatar
  • 121
1 vote
0 answers
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$ ...
zetaprime's user avatar
  • 123
1 vote
0 answers
36 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 &...
Alex Pharaon's user avatar
1 vote
0 answers
22 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 ...
Téo Bouvard's user avatar
1 vote
0 answers
69 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 ...
JoshHalas's user avatar
  • 203
1 vote
0 answers
51 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 ...
Retracted's user avatar
  • 141
1 vote
0 answers
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 ...
taktoa's user avatar
  • 364
1 vote
0 answers
48 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 ...
Zahradnik's user avatar
1 vote
0 answers
45 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 ...
luisfer's user avatar
  • 11
1 vote
0 answers
38 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 ...
Colin McDonagh's user avatar
1 vote
0 answers
312 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. ...
Alexander Weps's user avatar
1 vote
0 answers
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 ...
Dijenek's user avatar
  • 11
1 vote
0 answers
90 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 ...
John Smith's user avatar