# 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
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 ...
• 391
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 ...
• 378
43 views

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 ...
• 131
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$ ...
• 287
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 ...
325 views

• 532
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. ...
• 280
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....
• 237
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 ...
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 : ...
• 139
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 ...
• 395
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 ...
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 ...
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 ...
• 51
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$ ...
• 121