Questions tagged [sets]
Questions about finite and infinite sets and multisets, related data structures and concepts.
412
questions
2
votes
0
answers
23
views
Map-like data structure with subsets as keys
I am looking for a map-like data structure with the following properties:
it uses subsets of some set S as keys. The size of S is potentially unbounded, but does not change during the runtime
the ...
- 121
0
votes
0
answers
11
views
Trying to figure out how to model the structure of a multilingual dictionary for several constructed languages (basically Wiktionary for my conlangs)
Okay, so, this will be quite a bit, sorry. I'm working on several constructed languages for a worldbuilding project. Up until this point, I have been using a spreadsheet to store the vocab; each row ...
- 1
1
vote
1
answer
19
views
Is there a practical algorithm for estimating antichain coverage of a superset?
Suppose I'm given a set $S$ and antichain $A \subset 2^S$ ($\forall a_1,a_2\in A: a_1\neq a_2 \iff a_1 \nsubseteq a_2$).
Let's call subset $b \in 2^S$ covered by $A$ if $\exists a \in A :b \subseteq a ...
- 13
0
votes
0
answers
45
views
Sending set of string in HTTP query string
I'd like to implement pagination for an API. The elements are ordered by time but there can be multiple elements with the same timestamp. So there can be some duplication between the last elements of ...
- 101
1
vote
1
answer
48
views
How is the direct product of the functions (A -> B) * (C -> D) equivalent to the function (A * C) -> (B * D)? Is there an error here?
In the simply typed lambda calculus we have type algebra - types can be added, multiplied and exponentiated, where addition corresponds to the sum type, multiplication to the product type, and ...
2
votes
1
answer
57
views
What is the time complexity of removing among $N$ sets of size at most $n$ the sets which are subsets of another set?
A naïve solution would be to first sort all sets, taking time $O(N n \log n)$. Then, for every possible pair of sets, check if one is a subset of the other, and if applicable remove the subset. This ...
- 665
0
votes
5
answers
311
views
What is the difference between the set containing the empty string and the set containing nothing at all?
It's an exercise question from chapter 0 of Michael Sipser's book Introduction to the Theory of Computation.
e. The set containing the empty string
f. The set containing nothing at all
I guess the ...
- 11
0
votes
3
answers
56
views
Given two sets of coordinates, find out neighboring ones
I have two sets of 2-dimensional coordinates on an integer grid, $A$ and $B$
$A = \{(x_{A1},y_{A1}), (x_{A2}, y_{A2}), (x_{A3}, y_{A3}), \dots\}$
$B = \{(x_{B1},y_{B1}), (x_{B2}, y_{B2}), (x_{B3}, y_{...
- 181
1
vote
1
answer
39
views
4
votes
0
answers
53
views
Finding all sets which are not subsets of other sets
I have a set of sets, for example
{
{1, 2, 3},
{1, 2},
{2},
{2, 4}
}
I want to find all sets which are not subsets of another set. For example, ...
- 141
1
vote
0
answers
17
views
Randomly Split a Bar Into Beats
So I'm writing a software that generates random MIDI tracks based on a given mode, tonal etc.
As for now the randomisation works on tones building sequences of equal duration.
What I'd like to do is ...
- 111
-4
votes
2
answers
28
views
Let F be a function defined for all nonnegative integers by the following recursive definition
Let F be a function defined for all nonnegative integers by the following recursive
definition.
F(0) = 0, F(1)= 1
F(n + 2) = 2F(n) + F(n +1), n>0
Compute the first six values of F; that is, write ...
- 1
1
vote
1
answer
36
views
How to argue that an $A$-covering matching exists in this bipartite graph?
In lecture the following was mentioned in the context of matchings in bipartite graphs:
Let $U$ be a finite set and let $\mathcal{S}$ be a family of subsets of $U$.
For $u \in U$ let $r(u) := \lvert \...
- 457
0
votes
1
answer
57
views
Way to call and explain: "potentially infinite set of attributes" in databases
This is a bit of a theoretical question. I would like to know how to call the principle described below, in proper computer science terms, or math terms.
Let's say we have a database in which one ...
0
votes
1
answer
52
views
Logical Consequence - Equivalent Assertions
I have the following slide in my notes and I'm having trouble understanding how the three assertions are equivalent. I understand to a degree how the 2nd and 3rd assertions are equivalent, but the ...
- 1
0
votes
1
answer
30
views
Reconstruction of the universal set from disjoint subsets
Before I even attempt coming up with an efficient algorithm, I tried googling for similar problems but didn't get far, most queries mentioning "sets" in them led to some sort of Multiple ...
0
votes
1
answer
150
views
Suppose we have an empty alphabet Σ=∅, what are the possible languages of this alphabet?
Lets say the alphabet is Σ=∅,what are the possible languages of this alphabet?
According to my definitions:
I know that an alphabet is a finite set of symbols Σ
I know words is a set of all finite ...
- 3
0
votes
1
answer
22
views
Algorithm for allocating resources; one resource per one user who accepts it
I am looking for an algorithm for the following problem:
I have a set of users and a set of books.
Every user has their own set of favorite books, which may be empty, and is a subset the set of books.
...
- 113
0
votes
1
answer
72
views
Is there a computationally efficient algorithm which can map back and forth a multi-dimensional real number (R^n) to a single dimensional real (R)?
I believe its possible to achieve this with natural numbers.
The example below is for 2d to 1d conversions both ways, I do believe this generalizes to n-dimensions.
The mapping should work in a way ...
- 155
2
votes
2
answers
117
views
Find if a given number must be in a set that is closed under gcd and lcm with some given elements
Source: https://oj.vnoi.info/problem/cryptkey (problem statements are in Vietnamese, so here it is translated).
There is a set $S$ of positive integers. If $A$ and $B$ are in $S$, then $\gcd(A, B)$ ...
0
votes
2
answers
64
views
Why is $\{ w \in \Sigma^* : M_w[\epsilon]\downarrow \land |w| \leq 7\}$ decidable?
I get that the argument for this set $\{ w \in \Sigma^* : M_w[\epsilon]\downarrow \land |w| \leq 7\}$ to be decidable is that $|w|\leq7$ meaning it is a finite set and therefore it can be decided. ...
- 3
0
votes
1
answer
154
views
Does order of elements in a set matter in Dijkstra's Algorithm?
When we use a set for doing Dijkstra's Algorithm, we use a pair of {distance,node} which we insert in a set. Most of the articles say that the first element of pair should be the distance , else we ...
2
votes
0
answers
43
views
Lowest total cardinality mutually exclusive construction of a superset
Let there be $N$ sequences containing at least one set each. Each set has at least one element each.
Select exactly one set from each sequence. The selection within each sequence is mutually exclusive....
- 237
2
votes
1
answer
105
views
Efficient algorithm to count number of intersections of n sets
I've come across this problem when working on a personal project of mine. I need an efficient algorithm of counting the number of overlaps between all pair combinations of n sets.
Example:
Set a = [...
- 23
2
votes
2
answers
133
views
Dictionary with sets as keys where lookup can be set intersection
Normally, when working with dictionaries, we expect around O(1) complexity when we go to retrieve a value given the key (and when we insert). I work in Python, but this might apply to any dynamic ...
- 123
1
vote
1
answer
40
views
Find the largest subset of unpaired elements [duplicate]
I have a large list (around 200k) of element pairs (e.g. A-B, A-C, B-C, ...). How can I find the largest subset of elements amongst which none are paired?
Example ...
- 113
1
vote
1
answer
67
views
Pair points between to sets minimizing the global distance
I have two set of points in the plane or space, which could be for instance radar contacts over two successive scans. I'd like to pair them so that the sum of squared distances is minimal.
One ...
- 111
0
votes
0
answers
19
views
Algorithms for computing "optimal set growth order"
Imagine you have a collection of possible "components" (C) and a set of "recipes" assembled from those components (...
- 101
0
votes
1
answer
43
views
If $L$ is finite and $R$ is not regular, then $R\cup L$ is not regular
Prove/Disprove: If $L$ is finite and $R$ is not regular, then $R\cup L$ is not regular.
I think that this one is true, but I am stuck:
Since $R$ is not regular, it is infinite, so $R \cup L$ is also ...
- 5
0
votes
0
answers
30
views
Prove that a predicate is not computable
Prove that the following predicate is not computable:
$P_e(n) =
\begin{cases}
1 & \textrm{if } \phi_n(n) = e \\
0 & \textrm{otherwise}
\end{cases}$
Could someone explain how to approach ...
6
votes
0
answers
39
views
How to find the minimum number of elements to distinguish several given sets?
Given $n$ distinct sets $S_1, S_2, \cdots, S_n$, how to find a set $X$ such that $X \cap S_1, X \cap S_2, \cdots, X \cap S_n$ are still distinct, and the size of $X$ is minimum?
For example, given $\{...
Acesrc
0
votes
0
answers
74
views
Find non intersecting elements quantity of the few unknown sets
There is group of sets. All sets have the same number of elements. Elements are unknown, but I know sizes of operation results for each pair of sets. (union, intersection, symmetric difference, ...
- 199
2
votes
1
answer
27
views
Finding all combinations of length k that has at least one of the pairs of T is in it
Let there be a list of $n$ elements $S$. Let $T$ be a set with $m$ elements ($m \leq nC2$), with each element in $T$ being a pair of distinct elements of $S$. For $k\geq2$, is there a polynomial-time ...
3
votes
1
answer
64
views
Fast algorithm for computing minimal closure of a set of sets under intersection?
A step of an algorithm I’ve designed requires computing the minimal closure under intersection of a set of sets of arbitrary size. By the "minimal closure (of a set $S$) under intersection", ...
- 131
1
vote
0
answers
45
views
Prove that a dominating set has minimum cardinality in a "unit interval graph"
I am given the definition of a unit interval graph, e.g. $G = (V, E)$ such that $\forall v \in V$ there is a weight $x_v \in \mathbb{R}$ and nodes $u, w$ has an edge iff $|x_u - x_w| < 1$. I am ...
- 149
1
vote
1
answer
36
views
Locality Sensitive Hashing for Sets
Are there locality sensitive hashes that work nicely with sets? Each set would get a hash, the order of the elements in the set does not change the hash, and sets that share more elements are closer ...
1
vote
0
answers
55
views
Find sets which are subsets of the given search set?
The problem is the following:
You are given a collection( set, list, whatever ) C of sets, and you are given a search set S.
We want to find among all sets in C the ones which are subsets of S.
Hence, ...
- 121
3
votes
0
answers
147
views
Changing a family of sets to become laminar
A family of sets $F = \{S_1, \dots, S_n\}$ on the ground set $S$ is laminar, if for every $1\leq i < j \leq n$, either $S_i \subsetneq S_j$ or $S_j \subsetneq S_i$ or $S_i \cap S_j = \varnothing$ ...
- 287
0
votes
1
answer
47
views
Is the equality of Bloom filters analogous to set equivalence?
I have two multisets $A$, $B$ where $A \subseteq B$.
Using these two sets, we construct two Bloom filters $BF(A), BF(B)$; both using bitsets of size $n$ with the same $k$ hash functions.
What's the ...
- 123
1
vote
0
answers
49
views
Is there a distributed streaming algorithm to verify set cover?
I have $k$ sets of similar sizes, that cover a universe $U$.
e.g. for $k=3$ and $U = \{1, 2, 3, 4, 5, 6\}$:
$S_0 = \{1, 2, 4\}$
$S_1 = \{2, 3, 4\}$
$S_2 = \{4, 5, 6\}$
I have another larger set $C$ ...
- 123
1
vote
1
answer
31
views
DFA and a Partition of $\Sigma^*$
So I'm learning about Myhill-Nerode relations and as an introduction, the book describes possible partitions for $\Sigma^*$. As an example, given a language $L$, a partition of $\Sigma^*$ would be $\{...
- 29
0
votes
0
answers
33
views
How to generate supersets from a finite number of subsets efficiently
Let $F$ be a set, for instance $\{a,b,c,d,e \}$. Suppose I have a set of subsets of cardinality two obtained from $F$:
$ ${ a,b },$\{b,c\},${a,d}
I want to create every possible set of cardinality ...
- 111
2
votes
1
answer
140
views
Union of multiple overlapping sets efficiently?
I have $n$ sets, each of which overlaps heavily with the other sets, and I want the union of all of them. The obvious solution is to take the union of each set, one by one, which results in $O(n^2)$ ...
- 120
2
votes
1
answer
49
views
Is there a simplistic way of describing the proof to the undecidability of David Hilbert's 10th problem?
I recently have been reading a bunch about David Hilbert's famous 10th problem, and trying to understand its proof. I am currently in the process of reading through an explanation of the proof, given ...
- 145
2
votes
1
answer
83
views
Is this set covering problem NP-Hard?
Consider this variant of set covering problem.
Input: a collection of sets $S = \{s_1, s_2, \ldots, s_n\}$ and a universal set $U$, in which $s_k \subseteq U$ for all $k$.
The problem is, divide $S$ ...
- 69
1
vote
1
answer
53
views
How to efficiently see if a value is in a set
I was curious is there a really efficient way to see if a value is in a set? This question comes from me thinking about youtube views. As far as I understand youtube view count goes up for every ...
- 113
3
votes
1
answer
57
views
Deciding whether a set of relations can be composed to the empty relation
Is there an efficient algorithm to solve the following decision problem?
Given a finite set $S$ and a set of relations $\mathcal R$ from $S$ to $S$, determine whether there is any sequence of ...
- 83
1
vote
1
answer
325
views
Partition a set of n integers into m subsets in a way that the maximum subset sum is minimized
Let's say we have a set of n integers. I'm trying to find a way to partition this set into m subsets (empty subsets are not ...
- 53
1
vote
1
answer
99
views
set theory with RegEx on fen strings (or another parser)
how can you find if a regex call is a subset of another regex call on an predictable set of data
I have a string (chess Forsyth–Edwards Notation (FEN) string...
- 113
3
votes
1
answer
60
views
A heuristic for finding the vector that is maximally distant from a set of vectors
I have two sets of vectors: A and B. I want to find the vector Bi in set ...
- 103