Questions tagged [sets]
Questions about finite and infinite sets and multisets, related data structures and concepts.
301
questions
1
vote
1answer
27 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
20 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
45 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
28 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.
...
0
votes
1answer
69 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
36 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
50 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
48 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
17 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
25 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
28 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
91 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
53 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
45 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
94 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....
3
votes
1answer
47 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
30 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
44 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 ...
1
vote
1answer
100 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 ...
3
votes
1answer
47 views
Is it possible to determine if 2 arrays contain the same elements (ignoring duplicates) in faster than O(n log n) time?
So given 2 arrays of equal length, is it possible to determine whether the 2 arrays contain the same elements (ignoring duplicates and where those elements have a total order relation) with time ...
2
votes
1answer
22 views
How to find number of combinations of choosing one from k subsets
Consider we have set S:
S = {1,2,3,4,5,6}
and 3 (say k) subsets of S:
S_1 = {1,2,3}
S_2 = {2,3,4,5}
S_3 = {1,3,6}
What is the total number of cases choosing one element from each subsets?
Same ...
2
votes
1answer
34 views
largest bitwise-or subset with a maximum number of on bits?
Suppose I have the following set of bit sets:
...
2
votes
1answer
103 views
Hitting Set Problem with non-minimal Greedy Algorithm
The Hitting Set Problem is defined as having a universal set $\mathfrak{U}$, and nonempty sets $S_i \subseteq \mathfrak{U}$ for $1 \leq i \leq n$, and finding a set $\mathcal{H} \subset \mathfrak{U}$ ...
3
votes
1answer
32 views
A problem on sets
Given a collection C of sets, with union U, find a choice function which chooses a distinct element from each of the sets such that the union of the singleton distinct elements is U.
As an example, ...
2
votes
1answer
43 views
Efficient data structure for matching 3D lines
I'd like to
Store a set of many infinite undirected 3D lines.
Make lookups against this set - i.e. given an arbitrary line, ask "Does the set contain a line coincident with this one?"
The incidence-...
2
votes
0answers
74 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 ...
0
votes
2answers
50 views
How to partition disagreeable people into compatible groups
We have a number of people that must be partitioned into groups, but there may be people that dislike other individuals. Partition the people into the minimum number of groups such that no person is ...
1
vote
1answer
65 views
How can $A \cup B$ be decidable if $B$ is undecidable?
My assignment says:
"Determine if the following statement is correct:
If $A$ and $A \cup B$ are decidable, then $B$ is decidable."
The solution says:
"Incorrect. If $B = H_0 \subseteq \{0,1\}^*$ ...
3
votes
1answer
42 views
Proof of sparsification lemma: What exactly does the $\pi$ operator do?
In their proof of the sparsification lemma, Impagliazzo et. al describe the following operator $\pi$:
For a familiy of sets $\mathcal{F}$, let $\pi(\mathcal{F}) \subseteq \mathcal{F}$ be the family ...
0
votes
1answer
48 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 ...
3
votes
1answer
80 views
Lambda Calculus as a branch of set theory
This answer to a question about whether C is the mother of all languages contained an interesting tidbit that I am curious about:
The functional paradigm, for example, was developed mathematically (...
0
votes
0answers
25 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 ...
2
votes
1answer
115 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
75 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 ...
1
vote
1answer
171 views
Finding longest subset arithmetic progression with given difference
Given a list of distinct positive integers, I am trying to find the largest subset that forms an arithmetic sequence with a given difference D.
For example, given D = 5, with the set of numbers 1, 5, ...
0
votes
1answer
57 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
39 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
107 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
24 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
98 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
159 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
48 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
101 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
63 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
334 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
44 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 ...
3
votes
1answer
194 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
121 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
159 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, ...
