Questions tagged [sets]
Questions about finite and infinite sets and multisets, related data structures and concepts.
28
questions
6
votes
1
answer
951
views
Data structure for a static set of sets
I have collection $U$ of sets, where each set is of size at most 95 (corresponding to each printable ASCII character). For example, $\{h,r,l,a\}$ is one set, and $U = \{\{h,r,l,a\}, \{l,e,d\}, \ldots\}...
- 171
9
votes
2
answers
2k
views
Looking for a set implementation with small memory footprint
I am looking for implementation of the set data type. That is, we have to
maintain a dynamic subset $S$ (of size $n$) from the universe $U = \{0, 1, 2, 3, \dots , u – 1\}$ of size $u$ with
operations ...
- 3,005
7
votes
2
answers
2k
views
Concatenation of the intersection of two languages
I'm enrolled to a Formal Language And Automata course, and we have to prove this equation on sets of strings:
$$(L_1\cap L_2)\cdot L_3 ≠ (L_1\cdot L_3) \cap (L_2\cdot L_3)$$
I've tried a lot of sets ...
- 173
5
votes
1
answer
335
views
Finding containing sets in a set of sets
Suppose I have a set of sets of integers $A$, is there an efficient algorithm/data structure that will allow me to query for all sets of integers that include a given input set? That is, given input $...
- 6,171
4
votes
3
answers
12k
views
Is every subset of a decidable set, also decidable?
Is it true that if A is a subset of B, and B is decidable, than A is guaranteed to be decidable?
I believe it would be true because all the subsets of B should also be decidable making A decidable. I'...
- 165
23
votes
4
answers
9k
views
Data Structure for Set Intersection?
Is there any data structure that maintain a collection of set (of finite ground set) supporting the following operations? Any sublinear running time will be appreciated?
Init an empty set.
Add an ...
- 331
3
votes
1
answer
481
views
Asymptotic lower bound on the number of comparisons needed to find the intersection of unsorted arrays
A homework problem in my current CS class asks us to produce a comparison-based procedure for taking (essentially—there are some poorly-specified rules about duplicates) the set intersection of $k$ ...
- 409
3
votes
2
answers
188
views
Redistributing a set of uniformly distributed numbers to an arbitrarily defined shape
Lets say I have a random number generator that spits out uniform numbers from 0 to 1
Next, I have a shape defined by a series of vertices, like { [0, 0.4], [0.5, 0.2], [1, 0.4] }
In those vertices, ...
- 131
1
vote
1
answer
342
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 ...
-1
votes
1
answer
104
views
A max-even subset problem
I want to know if there is any polynomial algorithm for the problem, or any NP-completeness result.
Given a set $S$ and $m$ subsets $C_1, \dots, C_m$ of $S$, we want to find a non-empty set $X\...
52
votes
4
answers
7k
views
What exactly is the semantic difference between set and type?
EDIT: I've now asked a similar question about the difference between categories and sets.
Every time I read about type theory (which admittedly is rather informal), I can't really understand how it ...
- 3,472
16
votes
4
answers
9k
views
Given a set of sets, find the smallest set(s) containing at least one element from each set
Given a set $\mathbf{S}$ of sets, I’d like to find a set $M$ such that every set $S$ in $\mathbf{S}$ contains at least one element of $M$. I’d also like $M$ to contain as few elements as possible ...
- 267
15
votes
4
answers
5k
views
What exactly is the semantic difference between category and set?
In this question, I asked what the difference is between set and type. These answers have been really clarifying (e.g. @AndrejBauer), so in my thirst for knowledge, I submit to the temptation of ...
- 3,472
14
votes
4
answers
13k
views
Computing set difference between two large sets
I have two large sets of integers $A$ and $B$. Each set has about a million entries, and each entry is a positive integer that is at most 10 digits long.
What is the best algorithm to compute $A\...
- 241
12
votes
5
answers
1k
views
How to find the maximal set of elements $S$ of an array such that every element in $S$ is greater than or equal to the cardinality of $S$?
I have an algorithmic problem.
Given an array (or a set) $T$ of $n$ nonnegative integers. Find the maximal set $S$ of $T$ such that for all $a\in S$, $a\geqslant |S|$.
For example:
If $T$=[1, 3, 4, ...
- 960
12
votes
3
answers
22k
views
What is complement of Context-free languages?
I need to know what class of CFL is closed under i.e. what set is complement of CFL.
I know CFL is not closed under complement, and I know that P is closed under complement. Since CFL $\subsetneq$ P I ...
- 123
5
votes
1
answer
726
views
Finding set of disjoint sets with additional value optimization
I've got a set $Q$ of pairs $[S, v]$ where $S$ is a nonempty set and $v$ is a value ($v \in \mathbb{N}_{+}$). I need to find a subset $R$ of $Q$ with following properties:
Sum of all $v$'s is maximum
...
- 153
5
votes
1
answer
3k
views
Data structure for partition of a set
A partition of a set S is a separation of the set into an arbitrary number of non-empty, pairwise disjoint subsets whose union is exactly S. What manner of a data structure should be used to represent ...
user1448338
5
votes
1
answer
294
views
What is the name of this positive integer set data structure?
Google is failing me, so here goes:
The data structure is used to describe a set of positive integers.
It works conceptually, by keeping track of disjoint ranges [a,b) on the number line.
These ...
5
votes
0
answers
993
views
Time complexity of obtaining the set of distinct elements in a sequence?
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 ...
- 945
4
votes
1
answer
212
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 ...
- 143
3
votes
1
answer
737
views
How to read off the set represented by a van-Emde-Boas tree?
I'm reviewing my background in Algorithms and DS design. Specifically I never went through the van Emde Boas Tree. Though I can undestand the proto-vEB with related picture. I'm struggling to ...
- 683
3
votes
1
answer
1k
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 ...
2
votes
3
answers
926
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^...
- 125
2
votes
1
answer
65
views
Finding users covering a set x by x
I have a Set $S$ of objects, a set $U$ of users and a map $c: U \rightarrow S^{\prime}$, where
$S^{\prime} \subset S$ and $\emptyset \notin S^{\prime}$.
Every time I add a new entry to $c$, i.e. ...
2
votes
1
answer
121
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:
...
- 121
1
vote
1
answer
2k
views
How can you determine what set of boxes will maximize nesting?
I'm trying to find a dynamic solution to the nesting boxes problem.
You're basically given a set of "boxes" which all have different dimensions. The goal is to find the maximum set of boxes that can ...
- 121
0
votes
2
answers
384
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 ...
- 103