# Questions tagged [sets]

Questions about finite and infinite sets and multisets, related data structures and concepts.

436 questions
Filter by
Sorted by
Tagged with
8k 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,702
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
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 ...
• 351
6k 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 ...
450 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.5k
6k 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,702
10k 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 ...
• 277
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
14k views

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, ... • 990 12 votes 3 answers 23k 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 270 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 1k 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,078 9 votes 2 answers 9k 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,922 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 ... 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 651 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 986 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 170 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 1k 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
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 ...