Questions tagged [sets]
Questions about finite and infinite sets and multisets, related data structures and concepts.
331
questions
3
votes
0answers
24 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 ...
3
votes
1answer
110 views
How to detect “tree-able” set-families?
A set-family (a set of sets of elements) is called tree-able if the elements can be arranged on a directed tree such that each element appears in exactly one node, and each set in the family ...
2
votes
1answer
57 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 ...
0
votes
1answer
46 views
Combinations of set unions
I have a set $S = \{0,1,2,3,4,5,6,7,8,9\}$. $S_i \subset S$ for $i = {1,2,3,4,5}$. Any three $S_i$ has the same union, that is $S_1
\cup S_2\cup S_3 = S_1\cup S_2\cup S_4 = ...=S_3\cup S_4\cup S_5 = A$...
6
votes
2answers
161 views
Spanning tree in a graph of intersecting sets
Consider $n$ sets, $X_i$, each having $n$ elements or fewer, drawn among a set of at most $m \gt n$ elements. In other words
$$\forall i \in [1 \ldots n],~|X_i| \le n~\wedge~\left|\bigcup_{i=1}^n X_i\...
2
votes
1answer
92 views
Find two disjoint set
Given an universum $U$ and two sets $A$ and $B$ of sets of elements from $U$. I want to find (if such a pair exists) $a \in A$ and $b \in B$: $a \cap b \equiv \emptyset$. Currently I can do it only in ...
1
vote
1answer
24 views
Optimal Selection of Non-Overlapping Jobs
I'm trying to find what the family of problem is - as well as an approach - for the following:
I have a set of tasks T = [t1, ..., tn] to do, each of which has a corresponding reward ri.
Each task ...
1
vote
0answers
39 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 ...
2
votes
1answer
87 views
C++ STL: How does the distance() method work for a set/ multiset (stored internally as a self balancing tree)?
I'm working on the problem: Count smaller elements on right side using Set in C++ STL
The solution is to add each element to the set and then to count the elements on the left, the distance function ...
1
vote
1answer
50 views
Algorithm to check Gibbs' Phase Rule
I am looking for an algorithm to solve the following problem. I am unsure whether to post this in computational science or here, but since this is an algorithm I thought I would try here first.
I have ...
1
vote
1answer
39 views
Need hint for bipartiteness proof
I am given a graph $G = (V, E)$ with $N$ connected components and $G^\prime = (V^\prime, E^\prime)$, where for each $v \in V$ there is $v_1, v_2 \in V^\prime$ and for each $(u, v) \in E$ there is $(...
0
votes
1answer
43 views
Splitting a group of numbers into $k$ sorted groups
I have this first task:
You have a set of numbers $S =\{ \dots \}$ of length $n$.
And a number $k$.
Both $n$ and $k$ are powers of $2$ and: $1 < k < n$
Your task is to write an algorithm (...
1
vote
1answer
62 views
Sets in Mathematics are immutable but in Computer Science sets are mutable and called “Dynamic Sets” - truth of the statement
While reading the classic text Introduction to Algorithms by Cormen et. al. I came across the following claim:
Sets are as fundamental to computer science as they are to mathematics. Whereas ...
1
vote
0answers
31 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 ...
0
votes
1answer
51 views
What is the time complexity of subset testing?
Consider the following problem:
Let $A = \{a_1,...,a_n\}$ and $B = \{b_1,...,b_m\}$ be
two finite sets over $\mathbb{N}$. The sequences $a_1,...,a_n$ and $b_1,...,b_m$ do not have to be sorted.
...
0
votes
1answer
36 views
Is the empty string and some words of even length are elements of this set?
$L = \{w \in \{a,b\}^*| \text{the first, the middle, and the last characters of $w$ are identical}\}$.
I have my answers, but I need confirmation:
Is the empty string $\epsilon \in L$? Yes. Reason: ...
0
votes
0answers
19 views
Computing Follow sets of Grammar for LL(1) parser
I am trying to compute the Follow set of the following Grammar:
E -> E' E A
A -> + | *
E -> num
E' -> num
I start by adding the end of string symbol, ...
1
vote
0answers
33 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 ...
2
votes
1answer
21 views
Uniquely identifying bits
Query: Given $m$ unique integers smaller than $2^n$, can we keep at most $k$ the same bits of each number to uniquely identify them?
Is this problem NP-Hard?
For example, given the $4$ unique ...
0
votes
1answer
41 views
Elements of Programming Interviews - 16.4 Generate Power Set - solution 1 time complexity question
hope you all are doing well.
I have a question about the time complexity of solution 1 for question 16.4 - Generate Power Set from the book Elements of Programming Interviews by Adnan and Tsung-Hsien....
2
votes
1answer
24 views
Maximizing integer sets intersection (with integer delta)
There are two sets of integers with different numbers of items in them.
...
0
votes
0answers
22 views
Benefits of linked lists over forests for disjoint sets
CLRS discusses two specific data structures for disjoint sets:
Single linked lists, where each set is represented by a single linked list, and each node has two pointers, one to the list head and ...
1
vote
1answer
26 views
Efficiently finding the intersections of sets that yield a desired set
Given a collection of sets $\{S_1, S_2, \dots, S_n\}$, find all the "reduced" intersections between those sets that yield the desired set $\{x\}$ as the result. A "reduced" intersection is defined as ...
3
votes
1answer
56 views
How to generate, validate, and invalidate a set/list of numbers in O(1) time and space?
Imagine my server is generating "tokens" of some sort for a client on a regular basis. When a client asks for a token, the server responds with a new value (and any other supplemental information it ...
2
votes
1answer
29 views
Is there an algorithm to find the smallest set of the shortest prefix substrings of a continuous numeric sequence?
Before anything I want to preemptively thank anyone who drops by for their patience, I don't have any formal CS background so I'm probably going to use some of these terms wrong.
I have a puzzle: ...
2
votes
1answer
25 views
Data structure for or-lookups over bit-field associations maps
For a mapping between a bit-arrays and values I want cheap lookups using bitwise-or instead of equality.
Slightly more formally, I have a set of associations $k_i \mapsto v_i$ where $k_i \in \mathcal{...
1
vote
0answers
24 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 ...
3
votes
1answer
73 views
Smallest set of balls under hamming distance that covers all $n$-bit strings
Suppose we defined a set $S = \{x\mid0 \leq x \leq 2^n-1\}$. Notice that all element in $S$ can be represented with a $n$-bit binary string. Now consider subset $S_i$ such that,
$$S_{y_i} = \{y \in S\...
1
vote
1answer
77 views
Is the powerset of a regular set also a regular set?
If so, where can I find a proof of it? If not, is there a counterexample?
By powerset of a regular language I mean the set of all subsets of a regular language.
Thank you, Marcus.
3
votes
1answer
249 views
How to get an element from an existential proposition in Type theory proof assistant (Lean prover)
I am trying to implement set theory in type theory from scratch, just for self pedagogical purposes. Specifically, I'm using the Lean Prover, and defining the element-of relation from scratch using ...
1
vote
1answer
94 views
Generate all combinations of a set/array with specific conditions
Apologies if this isn't posted in the right stack exchange, but I'm trying to come up with an algorithm that generates a set of sets ('set' as synonymous with 'array') with the following conditions:
...
0
votes
0answers
21 views
Minimum pair-wise XOR of elements from two sets
I have two sets, $A$ and $B$, which both contain a large amount of hashed values.
What is the most efficient way of computing:
$$\min_{i,j} A_i \otimes B_j$$
1
vote
1answer
65 views
Overlapping between two intervals: reasoning / algorithm to find the set of disjoint and overlapping intervals
Consider the positive integers {1, 2, 3, 4, ...} and the corresponding Integer Number Line.
Suppose we have four integer numbers, A, B, C and D.
For example:
...
0
votes
0answers
55 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
1answer
427 views
Explanation of O(n2^n) time complexity for powerset generation
I'm working on a problem to generate all powersets of a given set. The algorithm itself is relatively straightforward:
...
0
votes
1answer
25 views
Given the Equivalence relation R = { x, y $\in$ $\Bbb{Z}$ : (x+y) mod 2 = 0}, what are equivalence classes 1 and 2?
Given the Equivalence relation R = { x, y $\in$ $\Bbb{Z}$ : (x+y) mod 2 = 0}, what are equivalence classes of 1 and 2?
I can't really see the equivalence classes of infinite sets. Only by having a ...
0
votes
1answer
43 views
Given a set of integers $D$ and a positive value$P$, find an algorithm to find set of integers satisfying a condition
Given a set of positive integers :
$ \\ D = \{ D_1, D_2, ..., D_n\}$
and a non-negative integer $P$, where $P$ is divisible by every element in $D$, then find ...
1
vote
1answer
52 views
Good algorithm to find all pairs of strings between 2 sets so that all words from the 1st string are all contained in the 2nd string?
I have 2 large sets of strings (actually they are product names). "Large" means few millions of strings.
Example:
Set 1:
...
1
vote
1answer
53 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
1answer
29 views
Algorithm to compute decomposition of a union of sets to a disjoint union of intersections
A union of sets can be decomposed into a disjoint union of intersections. Rather than writing confusing notation, this is easiest to to see in an example of three sets.
This clearly generalizes. If ...
1
vote
0answers
26 views
What is the maths name for a set which contains the Domain and Codomain of a function? [closed]
Im interested in this so that I can name a type parameter in a program I'm writing.
There is function that that has three parameters.
D, Domain
C, Codomain
X, where D is a subset of X and C is a ...
2
votes
1answer
31 views
Demonstrating that probability for every possible result is uniform at the end of an algorithm
I have memory of $k$ elements that you can imagine being represented by an array. One by one, the array receives a value corresponding to the time index, for example at $t=1$ the value will be $1$.
At ...
2
votes
1answer
132 views
How many different languages over the unary alphabet {a} are recognized by 2-state DFAs?
I am struggling to answer the following question:
How many different languages over the unary alphabet {a} are
recognized by 2-state DFAs?
According to the textbook, the hint was to first ...
0
votes
0answers
55 views
How to maximize $f$ while minimizing $g$ at the same time?
Lately, I have been dealing with a problem that I didn't know how to name it to solve it properly.
The problem is as follow: let's assume that we have a set of elements $A$. And, we have two ...
0
votes
0answers
50 views
Why is A(B ā© C) ā AB ā© AC? [duplicate]
I am told A(B ā© C) ā AB ā© AC
I am unsure as to why they are not equal. Using examples and following them I am unable to show that they are not.
e.g Let A = {m} B = {s, p} C = {p, r}
A(B ā© C) = A{p} =...
0
votes
2answers
100 views
How is the set of functions from ${\{a,b\}}$ to $N$ countable?
Assume a set of functions from ${\{a,b\}}$ to $N$
Where $N$ is the set of Natural numbers.
Let us assume that the size of $N$ is $n$.
i.e $|N|=n$
The first element $a$ have $n$ choices for mapping....
6
votes
1answer
90 views
Partitioning bag of sets such that each set in a group has a unique element
Suppose I have a bag (or multiset) of sets $S = \{s_1, s_2, \dots, s_n\}$ and $\emptyset\notin S$. I wish to partition $S$ into groups of sets such that within each group each set has at least one ...
1
vote
1answer
106 views
Given a set of sets, what is the largest common intersection between them?
Given a set of sets: $S = \{~\{1, 2, 3\}, \{2, 3, 4\}, \{1, 3, 4\}~\}$, I would like to find the largest common subset of $S$. If $S$ does not have a subset across all elements of $S$, I would like to ...
1
vote
1answer
46 views
Largest number of unique values in sets
Let's say I have 100 sets of values, and each set contains roughly 100,000 values. From these sets, I want to find the 10 sets that collectively have the largest number of unique values.
The brute ...
2
votes
1answer
292 views
Proving set of finite languages vs all languages over finite alphabet to be countable / uncountable
I came across following facts:
Set of finite languages over a finite alphabet is countable.
Set of languages over finite alphabet is uncountable.
I believe proof of this will be similar to ...
