The Stack Overflow podcast is back! Listen to an interview with our new CEO.

# Questions tagged [sets]

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

278 questions
Filter by
Sorted by
Tagged with
43 views

### An efficient method to compute a minimum set of sets that form the union of these sets?

Let's say we have a set of sets: $$\mathfrak S = \lbrace S_1, S_2, ... , S_n\rbrace$$ And the union of the all the sets in this set: $$\mathfrak U = \bigcup\limits_{i=1}^{n} S_{i}$$ And so there ...
42 views

### How can a set of N players be split into M teams, given certain rules?

A lot of times, I’ve needed to split a given set of people into a given number of teams but with some complications, like: Alice and Bob CANNOT be on the same team. Carol and David just HAVE TO BE on ...
317 views

### Find non-overlapping subsets that maximize the sum of their values

Given a set of elements $N$, a set $S$ of subsets of $N$, and a function $v:S \to \mathbb R$, determine a set $R\subseteq S$ of non-overlapping subsets that maximizes the total value. Has this ...
57 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 ...
96 views

### Datastructure for managing (abstract) sets

I am looking for a datastructure to represent the complex relationships between a bunch of abstract sets. The "abstract" means that these sets are not defined by their elements, but by their ...
31 views

101 views

### Sum of 2^Pi mod 1000000007 for all i where Pi is sum of numbers in ith subset of a set X [closed]

I am stuck on a problem in which I have to print sum of 2Pi mod 1000000007 for all i where Pi is sum of numbers in ith subset of a set X. Length of set can be upto 100000. Value of element in the ...
237 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(\...
43 views

### Given $n$ items with $k$ properties, construct a query that contains between $\frac {n} 3$ to $\frac {2n} 3$ items

I have $n$ items that have a total of $k$ properties. Each item can have any number of properties, from $1$ to $k$. There is no upper limit to k (the lower limit is $\lceil log(n) \rceil$). The items ...
27 views

### Determining whether a relation is the “union” of two other relations

Given a relations $P$ and $Q$ on $S$, what are the most efficient algorithms to find whether the relation satisfy the constraints $P \cup Q = S \times S$ and $P \cap Q = \emptyset$? If it helps, for ...
124 views

### Hash table where items can fall into multiple buckets. What's the name of the data scrtucture? [closed]

I have a task to search through an array of items. I want to narrow the search down to some partitions. I thought of hash tables, but the difference in my case is that the "hash-function" is not ...
130 views

### Representing multisets by a bit vector

What would be the most space-efficient way to represent a multiset (a set that can contain duplicates) using a (static) bit string (bit vector, bit array, etc.)? All of the elements in the multiset ...
133 views

### Sort complexity expressed via distinct number of elements

I am reading Probabilistic counting algorithms for database applications. In the introduction an algorithm for finding an intersection is specified: Sort A, search each element of B in A and retain ...
189 views

### Can a Turing machine determine if a set is accepted by a another Turing machine?

Can a Turing machine $M_A$ determine if the Turing machine $M_B$ accepts the set $W_k$? I am curious about the answer to this as I am thinking about using the truth value of it on using it for a ...
134 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 ...
116 views

35 views

### physical significance of membership function greater than one

In fuzzy logic, when we associate an element with a set, we usually do it in terms of membership grade which suggests the "belonging" of this element to the set. Membership grade value 0 means that ...
189 views

### Minimum number of sets of unreachable vertices for directed acyclic graph (DAG)

I have a DAG with vertices $V$ and edges $E$. If $v,w \in V$ are vertices such that $v$ is not reachable from $w$ and $w$ is not reachable from $v$, I will say that $\langle v,w \rangle$ is an ...
Given a set $S$ of length $n$, I'm looking to map all the $k$-length partitions of $S$ onto the set of integers such that these integers are as close to 0 as possible. Ideally the range would be \$\...