Questions tagged [sets]
Questions about finite and infinite sets and multisets, related data structures and concepts.
2
votes
1answer
113 views
Given N sets of disjoint subsets, find a set of disjoint subsets such that it satisfies a criteria
Given a collection of sets $S_i$ of disjoint subsets $sub_i$ of a set $X$,
find a set $A$ of disjoint subsets $asub$ such that each one of these subsets is subset or equal to at most one subset in ...
1
vote
1answer
427 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 ...
0
votes
1answer
35 views
Variant of the “Stable Roommates Problem” when room has not 2 but “n” mates
I'm looking at the name of a variant of the Stable Roommates Problem, when the rooms have more than 2 mates, ie for example 6 to 8. Does this problem has a specific name? A well-known algorithm?
To ...
0
votes
1answer
111 views
Prove/disprove that the class of decidable (resp. partially decidable) languages is closed under symmetric difference
Prove/disprove that the class of decidable (resp. partially decidable) languages is closed under symmetric difference. A symmetric difference of sets A and B is the set (A \ B) ∪ (B \ A).
I know that ...
0
votes
1answer
160 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
18 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
815 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 ...
11
votes
0answers
853 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
148 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
288 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
60 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 ...
2
votes
0answers
39 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
106 views
What is the deterministic time complexity of obtaining the set of distinct elements?
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
259 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
82 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
69 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
34 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
54 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
588 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
67 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
45 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
43 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
35 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
39 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
39 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
128 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
421 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
57 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
0answers
354 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
0answers
59 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 ...
