Questions tagged [sets]

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

Filter by
Sorted by
Tagged with
2
votes
1answer
112 views

Enumerating all set covers when knowing one set at least

I have an index taking as keys values from the power set $P(S)$ of a set $S$, except for $\emptyset$ and $S$. Then I have a query $Q=(s, k)$, where $s \in P(S) - \{\emptyset \cup S\}$ and $ 1 < k \...
6
votes
1answer
161 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 ...
2
votes
1answer
778 views

Set combination data structure (And storage complexity)

I have already posted this question on Stackoverflow, but I'm starting to think that this is the right place. I have a problem where I am required to associate unique combinations from a set (unique ...
0
votes
1answer
275 views

Is there a formula to state the number of 'sets' of 'ordered sets within ordered groups'?

I am new to this and an amateur... please help. My Question in practical terms: Given The three following inputs... determine the number of unique group arrangements as an ordered set. INPUT: 'a' = ...
0
votes
2answers
104 views

Computing every possible sum of integers taken from different sets

I'm trying to proove $NP$-membership for a problem from the following certificate. I have $n$ sets of integers : $$(S_i)_{i \in \{1,\dots,n\}}$$ Each set has a number $m_i$ of integers. I make "...
-2
votes
1answer
319 views

Subset product problems (one “easy” one “difficult”)

This question is from an exam preparation that I have to demonstrate to my teacher to show him that I understood the topic thoroughly . Given a set $S$ of integers with $n$ elements, an integer $z$ ...
3
votes
1answer
78 views

Find all items which are subsets of an item

I have a problem that I think should have been studied. I am looking for algorithms for it. Each item is a set of key-value pairs. Let $x$ be an item and $F$ be a set of items. Each key and each ...
7
votes
0answers
153 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 ...
1
vote
1answer
444 views

If $L = L(M)$ then $L$ is a subset of $L(M)$ and $L(M)$ is a subset of $L$

If $L = L(M)$ then $L$ is a subset of $L(M)$ and $L(M)$ is a subset of $L$. Can anyone clarify what does this mean?
17
votes
4answers
7k 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 ...
10
votes
1answer
707 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-...
6
votes
2answers
143 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 ...
2
votes
2answers
82 views

Regular language properties

For regular languages $R, S$ and $T$, which of the following are true? $R \cup S = S \cup R$ $(R \cup S) \cdot T = RT \cup ST $ $R^* \cdot S^* = (R \cup S)^*$
5
votes
2answers
12k 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 ...
3
votes
1answer
322 views

The use of multiset ordering in proving termination

Based on the definition of a multiset and the information in this paper, why do we use multisets in proving the termination of a program? Is not the well-founded order enough?
4
votes
1answer
628 views

Algorithm for determining minimal set of covering prefixes

I have a set of strings. My goal is to find a minimal set of longest prefixes which will match most of that set. For instance, if my set is: ...
5
votes
1answer
172 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 $...
1
vote
1answer
2k views

Multisets of a given set

A multiset is an unordered collection of elements where elements may repeat any number of times. The size of a multiset is the number of elements in it counting repetitions. (a) What is the number of ...
11
votes
4answers
233 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 ...
9
votes
3answers
13k 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 ...
3
votes
2answers
1k views

Cantor's diagonal method in simple terms?

Could anyone please explain Cantor's diagonalization principle in simple terms?
3
votes
1answer
145 views

Functions between sets?

I recently took a practice exam for the Computer Science GRE and this was one of the questions: Assume that set $A$ has 5 elements and set $B$ has 4 elements, how many functions exist from set $A$ ...
4
votes
1answer
225 views

Computing the rank of a multiset after inserting another element

What is the procedure for computing the rank of a multiset after inserting an element? For instance, lets say we have a set $S = (0,1)$ containing $n = 2$ distinct elements. The multiset $M = (1,1)$ ...
19
votes
1answer
376 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 ...
15
votes
4answers
6k 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 ...
5
votes
1answer
2k 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 ...