Questions tagged [sets]
Questions about finite and infinite sets and multisets, related data structures and concepts.
34
questions with no upvoted or accepted answers
11
votes
0answers
944 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 ...
7
votes
0answers
153 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 ...
3
votes
0answers
298 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 ...
3
votes
0answers
86 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 ...
3
votes
0answers
153 views
Time complexity of obtaining the set of distinct elements in a 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 ...
2
votes
0answers
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 ...
2
votes
0answers
41 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 ...
2
votes
0answers
306 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 ...
2
votes
0answers
93 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$ ...
2
votes
0answers
70 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 ...
2
votes
0answers
35 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 ...
2
votes
0answers
57 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 ...
2
votes
0answers
628 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 ...
2
votes
0answers
68 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 ...
2
votes
0answers
127 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 ...
1
vote
0answers
46 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
0answers
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 ...
1
vote
0answers
52 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
0answers
75 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.:
$$
\...
1
vote
0answers
42 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?
1
vote
0answers
135 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
0answers
453 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
0answers
58 views
Create the shortest list that contains a set of subsets in block
I have a problem where I have a set of subsets and I want to create the shortest list where I can find all subsets in it. Each subset must be a block of that list.
The input is a set of set of ...
1
vote
1answer
524 views
What happens if the associativity level is greater than the cache size?
I am working on a computer organization caching problem
The Problem: What happens if the associativity level is greater than the cache size?
I know that associativity level is how many blocks are ...
1
vote
0answers
363 views
Show that every infinite recursive set has both a nonrecursive r.e. subset and a non-r.e. subset
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 $\...
1
vote
0answers
37 views
How to find the accuracy of a set partitioning?
Suppose that there are $k$ sets $S_1, S_2, S_3, \dots, S_k$.
The numbers $N = \{1, 2, \dots,n\}$ are distributed into these sets equally.
Say that we partition $N$ into $m$ sets $P_1, P_2, \dots, ...
1
vote
0answers
25 views
Given a set of sets and a storage area, find an order that minimizes the sum of the differences between each set and the storage area
This problem is based on an order picking problem with a forward area.
The problem description is as follows. We have a warehouse with a set of items $I$ and a forward area $F$ of size $k$. Each day,...
0
votes
1answer
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 ...
0
votes
0answers
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 ...
0
votes
0answers
79 views
Pruning a powerset based on a graph
I have a list of nodes l = [1, 2, 3, ... , n] and a list of tuples p = [(1, 2), (2, 3), ...], where the latter represents which ...
0
votes
0answers
116 views
Algorithm: How many symbols of occurence k fit into b buckets under condition
I have the following problem to solve:
Given a set of buckets $B=\{b_0,\dots b_n\}$ of known size, a constant $k$ < |B| and a set of symbols $S=\{s_0,\dots, s_?\}$ with unknown size.
Place ...
0
votes
1answer
212 views
What does the symbol “::” mean in computer science?
What does the symbol $::$ mean in the following statement?
$\forall{x}\in K :: x \longrightarrow x$
A cycle in a graph is a path that starts and ends on the same node.
Clearly, if nodes in K lie on ...
-1
votes
1answer
20 views
Count points on same distance from set of points
Let's consider finite grid of points with size of $N$ by $M$ and set of $x$ points ($x$ is small number, up to 10, $N$ and $M$ are big numbers, up to 30000 )). Each of the $x$ points is described with ...
-1
votes
1answer
840 views
Finding number of maximum independent sets in tree, using dynamic programming
I'm quite stuck trying to answer this. The problem of finding the size of the maximum independent set in a tree using dynamic programming is well documented and many solutions are around.
I've been ...
