Questions tagged [sets]
Questions about finite and infinite sets and multisets, related data structures and concepts.
412
questions
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
29
votes
5
answers
6k
views
Boolean search explained
My mother is taking some online course in order to be a librarian of sorts, in this course they cover boolean searches, so they can search databases efficiently, however, she got a question sounding ...
- 393
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
21
votes
7
answers
5k
views
in O(n) time: Find greatest element in set where comparison is not transitive
Title states the question.
We have as inputs a list of elements, that we can compare (determine which is greatest). No element can be equal.
Key points:
Comparison is not transitive (think rock ...
- 319
19
votes
1
answer
445
views
Problems for which algorithms based on partition refinement run faster than in loglinear time
Partition refinement is a technique in which you start with a finite set of objects and progressively split the set. Some problems, like DFA minimization, can be solved using partition refinement ...
- 22.3k
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
2
answers
1k
views
Recover a set with the information of the sums of all its subsets
I have a set $S$, which contains $n$ real numbers, which generically are all different. Now suppose I know all the sums of its subsets, can I recover the original set $S$?
I have $2^n $ data. This is ...
- 283
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
11
votes
4
answers
268
views
Finding "fingerprint" sets
Let's say we have 10 people, each with a list of favorite books. For a given person X, I would like to find a special subset of X's books liked only by X, i.e. there is no other person that likes all ...
- 176
11
votes
1
answer
983
views
What is a compact way to represent a partition of a set?
There exist efficient data
structures for representing set
partitions. These data structures have good time complexities for operations
like Union and Find, but they are not particularly space-...
- 213
11
votes
0
answers
1k
views
Alternative to Bloom filter for extreme parameters
A Bloom filter is a space-efficient probabilistic data structure to perform membership-tests on a set (see Wikipedia's page for a definition; I use the same notations below).
I am interested in a ...
- 391
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
9
votes
2
answers
8k
views
Equivalence of independent set and set packing
According to Wikipedia, the Independent Set problem is a special case of the Set Packing problem. But, it seems to me that these problems are equivalent.
The Independent Set search problem is: given ...
- 5,808
7
votes
2
answers
1k
views
Is the intersection of infinitely many recursive sets recursive?
Is the intersection of infinitely many recursive sets $\bigcap_{i}U_{i}$ (where each set is different ) recursive? Recursively enumerable?
I know the union need not be recursive, because deciding if ...
user43288
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
7
votes
2
answers
645
views
Finding a fixed-size set whose members are contained by the largest number of other sets
I've been thinking about a problem, inspired by meeting a beginner-level foreign language professor at the Goethe-Institut who learned the five most common languages spoken by students in order to ...
- 173
7
votes
2
answers
956
views
Existence of Efficient Set Difference Algorithm
As a foreword, I'm not asking what the algorithm is, just whether one can possibly exist (though, if it does already exist and someone knows what it is, that'd be great).
Basically, given two sets $S$...
- 223
7
votes
0
answers
166
views
Overlap Maximization problem
Here's the problem:
I have a collection of collections, $C$, where each $c\in C$ is a collection of sets $X\subset U$. Denote $c_i$ as the i-th $X$ in $c$. Informally, I want to map all the sets in ...
- 378
6
votes
1
answer
180
views
Name for concept: each pair of sets is either nested or disjoint
Does this property have a name?
Given a collection of sets $\mathcal{P}$, for all pairs $A, B\in\mathcal{P}$, either $A\cap B=\emptyset$ or $A\subseteq B$ or $B\subseteq A$.
This concept could ...
- 20.1k
6
votes
2
answers
988
views
Efficiently finding $k$ smallest elements of Cartesian product
Given lists $A_1, A_2, \dots, A_n$ of non-negative numbers, I want to find the $k$ smallest elements of the Cartesian product $A_1 \times A_2 \times \dots \times A_n$ ordered by the value $x_1 + x_2 + ...
- 173
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
6
votes
1
answer
2k
views
Find an algorithm that finds a minimal hitting set for sets limited in size
Given a family of sets $F=\{S_1,...,S_m\}$, where $S_i{\subseteq}\{1..n\}$, with the assumption that the maximum size of any set $S_i$ is at most $k$ ($|S_i|{\leq}k\ {\forall}i\in\{i..n\}$).
I'm ...
- 163
6
votes
2
answers
177
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\...
- 353
6
votes
1
answer
178
views
Shared Elements Algorithm
I have a problem that I am working on an algorithm for:
I have $k$ sets of distinct positive integers (each set is distinct, not necessarily across sets)
$S=\{A_1,A_2,A_3,...,A_k\}$ where $\forall A_i\...
- 61
6
votes
1
answer
108
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 ...
- 12.5k
6
votes
1
answer
65
views
Small world theorem for set constraints
Let $S_1,\dots,S_n$ be variables representing unknown sets. A set expression has the form $S_i$, $\overline{E}$ (the complement of $E$), or $E \cap E'$, where $E,E'$ are set expressions. A ...
D.W.♦
- 150k
6
votes
2
answers
147
views
Test if there are two subsets which cover a set
Given a set $S$ of $n$ elements, and a set $\mathcal{X}$ of $m$ subsets of $S$, decide if there exist $U,V \in \mathcal{X}$, s.t. $U \cup V = S$.
Brute force would take time $O(nm^2)$ but is there ...
- 783
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
5
votes
2
answers
21k
views
Finding the minimum subset of intervals covering the whole set
Suppose we have a set $A$ of pairs $(a,b)$ such that $a$ and $b$ are real numbers and $a < b$. What is the most efficient algorithm to find the smallest subset $B \subseteq A$ such that, for any ...
- 369
5
votes
2
answers
795
views
Application of set theory subjects as ordinals, forcing, generic filters in software engineering
I am going to teach a course in set theory for software engineering students.
I am going to talk in this course about: ordinal numbers, partial orders, well ordering, generic filters and maybe some ...
- 153
5
votes
1
answer
135
views
Is there a formal difference between $f:X \to X$ and $f\in X \to X$?
We can denote by $X\to X$ the set of all functions from $X$ to $X$.
Therefore, we can use the following statement to say that $f$ is a function from $X$ to $X$:
$$f\in X\to X$$
But we usually state ...
- 3,472
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
3
answers
558
views
How to enumerate a product set?
I am coding a procedure that takes an integer $d$, and generates $d$ finite lists $X_1 \ldots, X_d$ of elements. I would then like for it to output a list of the elements in the product set $X_1 \...
- 51
5
votes
1
answer
250
views
How to find a minimum set of axioms within a set of propositions?
I have a set of propositions, for example $\{a_1,a_2,\dots,a_n\}$. Some propositions depend on others (for example, $a_1,a_2\Rightarrow a_3$, means if $a_1,a_2$ are true, then $a_3$ is true). I want ...
- 153
5
votes
1
answer
213
views
Introduction to type theory for a beginner?
I'm interested to read about type theory, but I'm quite a beginner. I know what sets are and how to work with them, but I don't have a deep understanding of set theory. I don't really understand the ...
- 3,472
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
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
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
5
votes
1
answer
60
views
Among a number of sets, how to find the one that includes the highest number of other sets?
I have a large number of sets, A, B, C, ... where each set includes a few integers. I would like to find the set that includes the highest number of other sets.
A ...
- 153
5
votes
1
answer
628
views
Maximize product of sum of two subset
Given two sets $A = \{a_1, a_2, \dots, a_n\}$ and $B = \{b_1, b_2, \dots, b_n\}$, both consist of positive numbers, this problem is to find a subset $S$ in $\{1, 2, \dots, n\}$ to maximize
$$
\left(\...
- 151
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
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
4
votes
2
answers
2k
views
Returning a random subset with length k of N strings while only storing at most k of them
Here's the problem. I've written a program that reads strings from stdin, and returns a random subset of those strings. The only other argument provided to the program is the length of the subset, $k$....
- 143
4
votes
3
answers
619
views
My algorithm is different from CLRS' -- is it wrong?
Exercise 2.3-7 from "Introduction to Algorithms" by Cormen et al. Third Edition, states:
Describe a O(n lg n)-time algorithm that, given a set S of n integers and another integer x, ...
user52157
4
votes
3
answers
1k
views
Data structure to store sphere points (latitude,longitude) and retrieve all points within a distance
I have a set of thousands~millions of points on a sphere's surface, each with latitude, longitude.
I want to quickly get all points within a distance d of a ...
- 143
4
votes
1
answer
152
views
What does $\{$ a set $\}^{+}$ mean in the context of languages?
I came across this notation and I don't know the meaning of it, or if it's a typo: $\{$ some set $\}^{+}$
What does the + mean, i.e., the plus operator applied to a set?
user16480
4
votes
2
answers
85
views
Finding the number of ways to partition $\{1,...,N\}$ into $P_1$ and $P_2$ such that $sum(P_1) = sum(P_2)$ for a given $N$
I am trying to think of how to optimize the following problem:
Let $S = \{1,2,...,N\}$. How many ways can $S$ be partitioned into non-empty subsets $P_1$ and $P_2$ such that $sum(P_1) = sum(P_2)$? I ...
- 143