Questions tagged [sets]
Questions about finite and infinite sets and multisets, related data structures and concepts.
2
votes
1answer
64 views
Suggest a Data Structure To Manage 2 Sets
I was given the following problem which really baffled me, and I would like some guidance in solving it.
I want to make a data-structure which represents two sets $A,B\subseteq \mathbb{R}$, so that I ...
3
votes
1answer
51 views
Fast hash function for set equality
I'm searching an hash function for integer set equality that must be fast.
It must support update (adding an element already in the set must not change the hash) and union.
MinHash has these 2 ...
0
votes
1answer
37 views
How do you compute the Pareto Front of a set?
I need to decide which solution is the best design, in order to do that I need to compare them. Lower energy used and lower weight is better. My initial idea was to order both the fields best to worst ...
1
vote
1answer
22 views
Complexity of set partition generation while equivalence relation is given
Given a binary equivalence relation, R on a set A, Let P be the resulting partition. I want to generate the partition means each subset in the partition. What would be the fastest algorithm for this ...
0
votes
1answer
49 views
Find all subsets with a given sum
How to choose from a set of positive numbers all the subsets that sum to some number x?
For example if the set $S=[1,1,2,3,4,5,6,7]$ and I'm searching for all the subsets that sum to $7$ I would have $...
1
vote
1answer
18 views
Name for multiset with fractional amounts?
What do you call a set which accepts multiples of the same element, even in fractional amount? Is there even an established for this?
Example from a video game about production chains:
For a ...
0
votes
1answer
41 views
Finding combinations of variables that can take value of -1/0/1 that produce sum of 0 with added constraint
I have 64 variables that can either take a value of -1, 0, or 1 and I am interested in finding all possible combinations of variables such that I have n variables in each the positive and negative ...
3
votes
1answer
51 views
Distinct elements count of huge multiset
I know that HyperLogLog can approximate the distinct elements count of a huge multiset but I was wondering if it was possible, using a method I saw mentioned on an IRC channel, to get an exact answer ...
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 ...
2
votes
2answers
90 views
What does the intersection symbol (∩) mean when applied to two non-set elements?
I came across a piece of literature in which I saw the intersection symbol (∩) being used on two non-set elements in the definition of an equivalence relation; I have posted it below for reference. ...
2
votes
1answer
53 views
Basic Set Theory problem
So i'm relatively new to computer science and have been learning set theory and am stumped on a question in it.
The question specifies that we're only looking at subsets of universe U = {0,...,n-1}. ...
-2
votes
1answer
108 views
Count the number of subsets with product less than or equal to k [closed]
You are given an array $A$ of $n$ positive integers, you have to find the number of subsets the product of whose elements is less than or equal to a given integer $k$.
Is there an efficient algorithm ...
1
vote
1answer
22 views
Identifying the Equivalence Classes of a Language with equal number of 10 and 01 strings
I'm doing a problem where I need to find the equivalence classes of the language below:
Let A = {x ∈ {0, 1}* | #(01, x) = #(10, x)}, where, for a, b ∈ {0, 1}*, #(ab, x) is the number of places in x ...
2
votes
1answer
71 views
Union of infinitely many regular languages [duplicate]
I need to prove or disprove the following statement.
If $A_n ⊆ \Sigma^*$ is regular for each $n \in \mathbb{N}$ then $\bigcup\limits_{n=0}^{\infty} A_n$ is regular.
I know that if two languages ...
0
votes
1answer
81 views
Proving the singleton language {x} is regular for all x ∈ Σ*
So I'm aware that the singleton language is in fact regular for all x ∈ Σ*, but I do not understand why it is. A formal proof would help, but also getting some intuition as to why it is regular would ...
2
votes
2answers
84 views
Proving that Every Full Prefix-Free Language is Maximal
I'm practicing a problem where I need to prove that every full prefix-free language is maximal.
I know a prefix-free language A is maximal if it is not a proper subset of any prefix-free language, ...
1
vote
1answer
29 views
Proving existence results
I'm doing a problem where I need to prove that there is a language A ⊆ {0, 1}* with both of the following properties:
(i) For all x ∈ A, |x| ≤ 5.
(ii) Every DFA that decides A has more than 8 states....
1
vote
1answer
31 views
$A^* = B^*$ with $\{0,1\}$ contained in $A$ but not in $B$
I'm trying to exhibit two formal languages $A,B ⊆ \{0,1\}^*$ such that $A^* = B^*$ and $\{0,1\}$ is contained in $A$ but not in $B$.
Finding a language for $A$ is very easy, but I get stuck on $B$, ...
1
vote
1answer
60 views
Proof of an Infinite Binary Sequence
I have a problem where given an infinite binary sequence S ∈ {0, 1}∞ to be "prefix-repetitive" if there are infinitely many strings w ∈ {0, 1}*
such that ww is a prefix of S.
I need to prove that if ...
1
vote
4answers
82 views
Proving B* = B on a given set
I have the set:
B = {x ∈ {0,1}* | there is an equal number of 0's and 1's in x}
and therefore,
B* = {e,01,10,0011,0101,0110,1100,1010,1001,....etc}
I need to either prove or disprove that B*=B
I ...
0
votes
1answer
34 views
Proving $A^\ast = A$ on a given set
I am working on some set theory and am trying to prove how a set can have the property $A^* = A$.
For set $A=\{0^n1^n \mid n \ge0\}$, I still do not understand exactly what $A^*$ is. For example, I ...
0
votes
1answer
28 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 ...
2
votes
3answers
153 views
N subsets with a given sum?
How to efficiently ¹⁾ choose from a set of numbers $S$, a given number $n$ of disjoint subsets, each with a given sum $K$ of chosen elements?
¹⁾ Not as in $P$, I just want something smarter than $O(n^...
1
vote
0answers
42 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
1answer
40 views
Can You List the Names of Some Algorithms For Determining the Intersection of Two Context Free Grammars?
Suppose we have two sets of strings XS and YS such that set XS is described by grammar GX and YS is described by grammar GY.
We want an algorithm which accepts GX and Gy as inputs. The algorithm will ...
2
votes
1answer
41 views
Find four sets where each element from those four appears in at least two of those four sets
I have a list of sorted arrays ("sets") of integers $A_1..A_n$ where each element is unique w.r.t. the other elements in the same array:
$A_i = \{x_{i,1}..x_{i,c_i}\}$
$x_{i,p} < x_{i,p+1}$
$A_i$ ...
3
votes
2answers
59 views
Given a set $A$ of sets find a minimal set $B$ of pair-wise disjoint sets such that each set in $A$ can be expressed as a union of sets in $B$
I recently thought of the following problem:
Given a set $A$ of sets find a minimal set $B$ of pair-wise disjoint sets such that each set in $A$ can be expressed as a union of sets in $B$.
For ...
1
vote
2answers
116 views
set cover where only certain special subsets are allowed
I am trying to solve a problem which turns out to be a form of the set cover problem. I've implemented the greedy Set cover approximation algorithm for set cover, but it turns out to not be accurate ...
1
vote
1answer
28 views
Is a set $B = \{y, \exists x \in A, f(x)=y\}$ recursive if A is a recursive set and f is a $N->N$ total computable function?
Obviously, B would be recursive if for every TCF f, there was an inverse fuction that would return all possible values, as we could just take these and then check if any of them is in A. However I ...
2
votes
1answer
60 views
Minimal set of subintervals that 'covers' any subinterval in K subintervals
I have a big interval $I = [a, b]$ of size n.
I want an asymptotically minimal set of subintervals of $I$ (let's call it $S$) one can use to construct any subinterval of $I$, by concatenating at most ...
3
votes
1answer
51 views
Algorithm / data structure to filter documents by number of missing words
Is there a data structure or an algorithm or a combination of both to allow me to filter a set of documents based on the number of missing words (compared to another list)?
Problem Definition
We ...
2
votes
1answer
50 views
Parser theory: How to systematically compute FOLLOW sets?
Forgive me for my ignorance as I am self-teaching myself some of this theory... I am having some trouble understanding how to systematically/algorithmically compute FOLLOW sets, given that I have ...
1
vote
1answer
45 views
PL: What solves the type isomorphism $X \cong (X \rightarrow \mathbf{2})$?
In Practical Foundations for Programming
Languages, on page 138 (page 156 of the pdf), it says:
Requiring solutions to all type equations may seem suspicious, because
we know by Cantor’s Theorem ...
0
votes
1answer
100 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 ...
1
vote
0answers
32 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 ...
3
votes
0answers
285 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 ...
2
votes
1answer
97 views
What is the algorithm for a decider to get the language accepted by a DFA?
I am trying to understand the larger problem of the decidability of the equality of two DFAs. I understand that this problem can be solved using minimizing DFAs, but my textbook states this can be ...
1
vote
1answer
45 views
How to find sets of polynomially bounded numbers whose subset sums are different?
Let $n$ be any positibe integer and set $N=\{1,\dots,n\}$. Now select two arbitrary but different subsets of $N$, say $S$ and $S'$. We are interested in finding a function $\pi(A)=\sum_{i\in A}a_i$ ...
2
votes
2answers
301 views
Prove: Every decidable set is Turing reducible to the empty set
Question-
Prove: Every decidable set is Turing reducible to the empty set.
Can anyone help me with this please?
All reductions tutorials I've seen use practical examples of reduction such as sipser'...
1
vote
1answer
78 views
Is it possible to add every word in a file to a set in $\mathrm{O}(n)$ time?
The Problem:
I am currently analyzing a simple program that takes a file of length $n$, splits it into its individual words (seperated by white space) and adds those words to a set:
...
1
vote
1answer
50 views
For each given set choosing either it or its complement such that their union exactly has a given size
Given an integer $k$ and $n$ sets $A_1,\ldots,A_n$, denote $U=A_1\cup A_2\cup\cdots\cup A_n$, $A_i^0=A_i$ and $A_i^1=U\backslash A_i$. The problem asks whether there exists $(b_1,\ldots, b_n)\in\{0,1\}...
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.:
$$
\...
2
votes
1answer
91 views
Find 2 sets with an empty intersection
I have the following problem. The problem can be formulated in three different ways
Given sets $B_{-n},\ldots,B_n \subset \{1,\ldots,m\}$.
Find $i,j \in \{-n,\ldots,n\}$ with $|i| \neq |j|$ and $i,...
0
votes
1answer
37 views
What is the optimal algorithm for finding all sets of overlapping ranges?
I have a set of (integer) ranges and want to compute the (possibly non-disjoint) set of all subsets of overlapping ranges. The data structure used for the output is not of particular importance to me; ...
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 ...
1
vote
1answer
45 views
number of random sets needed to generate subset
Let $A\subseteq \{1\ldots n\}$ with $|A|=\alpha n, 0<\alpha\leq1$. Now we start generating random sets $B_i \subseteq \{1\ldots n\}$ with $|B_i|=\beta n$ where $0<\beta\leq\alpha$.
How many $...
0
votes
2answers
844 views
Given n numbers How to find out a set of numbers whose sum equal to a certain given number
I am given an list of numbers and A number-s. I need to find out the collection(s) of numbers from the list of numbers whose sum corresponds to the given number s.
...
0
votes
0answers
19 views
What does it mean for a set to be NP-complete? [duplicate]
For homework I have the task
Assuming P ≠ NP, is the following set NP-complete:
{(G,w) | G is a Graph and w is a Hamilton cycle in G}
and I don't understand how to show that a set is NP-complete.
I ...
1
vote
1answer
28 views
complexity of outputting the union of a collection of subsets of a set
This question concerns the time complexity of outputting the unions of subsets of a given set.
Given $m$ subsets of an $k$-element set, can the union of those sets be computed in linear time with ...
1
vote
1answer
117 views
Print all subsets of a set ($a$) of $n$ positive integers, such that the product of their elements equals $p$
I have the following problem:
Given a set a of n positive integers, write a backtracking C function that prints out all the subsets of a such that the product of their elements is p. Use an array ...
