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.

Filter by
Sorted by
Tagged with
2
votes
1answer
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 ...
2
votes
1answer
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 ...
3
votes
2answers
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 ...
6
votes
1answer
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 ...
4
votes
2answers
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 ...
2
votes
1answer
31 views

Minimum number of intersections to arrive at specific set

Say I have a large number of sets (on the order of ~1000) with a smaller number of potential entries (~200), and a widely varying number of entries per set. An example: $s_1 = \{1, 42, 133\}$ $s_2 = ...
1
vote
1answer
45 views

Logic, “and” operator between a set of formulas and a formula

Consider a set $S$ of formulas $\beta_i$ and a formula $\alpha$, if we have a condition such as $S \land \alpha$ is inconsistent what we have to calculate to check the inconsistency of $S \land \alpha$...
3
votes
1answer
42 views

Algorithmic complexity of a Maximum Capacity Representatives variant

I have been trying to find the algorithmic complexity of a problem that I have. I am almost sure it is either NP-hard or NP-complete but I cannot find any proof. Recently, I found that my problem can ...
3
votes
2answers
694 views

Efficient implementation of sets

Let U be a pre-determined and fixed universal set (and |U| = n = 2k for some integer k, so the set may be huge). I create many arbitrary subsets of U in running time (These sets may be or may not be ...
1
vote
1answer
406 views

Subset partition problem variant

Given a set S of integers, the task is to partition the set into subsets such that: Total number of partitions is maximized Each partition has sum at least K This looks like a variant of bin-packing ...
1
vote
0answers
42 views

Smallest set non-disjoint with other given sets

Given a number of sets, what is the best algorithm to calculate the smallest set S such that S is not disjoint with any of the given sets?
3
votes
1answer
324 views

Subset of numbers whose XOR has least Hamming weight

I'm given $n$ numbers (let's say of some 100 bits or so). Is there a way to find a non-empty subset xor of these $n$ numbers which has the least Hamming weight (no. of set bits) in better than $O(2^n)$...
3
votes
1answer
39 views

Fewest induced subgraphs of order <= k which cover every edge

I'm facing a graph problem and I'm looking to identify it, maybe as a special case of a more general problem, so that I can then find an approximation algorithm for its solution (I'm assuming it's NP-...
0
votes
1answer
252 views

cardinality of recursive/r.e/not r.e languages? [duplicate]

I was just looking into properties of languages and wondered about the cardinality of them are all recursive languages countable or can they also be uncountable (can u have a recursive language which ...
2
votes
1answer
92 views

Finding maximal independent sets in an independence system

An independence system is a collection $I$ of subsets of $\Omega$ such that if $A\in I$, then any subset of $A$ is in $I$. These sets are called independent. Suppose I have an oracle for testing ...
0
votes
1answer
190 views

What does the symbol “::” mean in computer science?

What does the symbol $::$ mean in the following statement? $\forall{x}\in K :: x \longrightarrow x$ A cycle in a graph is a path that starts and ends on the same node. Clearly, if nodes in K lie on ...
2
votes
2answers
65 views

Unique representation of 5-number sets with values 1-13

From a simulation I get 5 numbers 1-13. The nature of the simulation is that I do not get the numbers ordered. The value/rank of the the tuple is not order dependent 5 5 5 2 2 = 2 5 2 5 5. Values ...
2
votes
0answers
70 views

Finding subsets in a large collection of sets

Given a large collection $\mathcal{X} = \{X_1, X_2, \dots, X_n\}$, where each $X_i$ is a set of integers, what's a fast algorithm to identify all pairs $(i,j)$ with $i \ne j$ such that $X_i \subseteq ...
2
votes
1answer
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 ...
5
votes
1answer
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(\...
2
votes
1answer
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 ...
1
vote
1answer
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 ...
1
vote
1answer
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 ...
1
vote
0answers
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 ...
2
votes
2answers
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 ...
2
votes
2answers
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 ...
5
votes
1answer
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 ...
2
votes
1answer
116 views

Equivalent expression in English: Set Notation $\{0,1\}^K$

I am overviewing this expression given in set notation. Could someone translate what M "Element of" $\{{0,1}\}^k$ stands for? Im looking for an explanation in English like what I did below. $K_e = \...
1
vote
1answer
42 views

Find K-subset that includes the most W-subsets

I have a set $S$ of $N$ elements, and a set $\Sigma$ of $N$ subsets of $S$: $\sigma_0, \ldots, \sigma_{N - 1} \subset S$, each with $W \ll N$ elements. Subsets can overlap partially or totally. For ...
1
vote
0answers
358 views

What is the best way to prove (S+)+ = S+? [closed]

Lets say I have the below language: S = {a, b} So if we apply Kleene plus to that language, it is something like: ...
2
votes
1answer
42 views

Algorithm to get maximal selection set of a collection of sets with a binary relation

I have a finite collection of finite sets $\{A_i\}_{i \in I}$. There is a relation $R$ defined on the elements of those sets (which is not transitive, it is irreflexive, and it is symetric). Suppose ...
1
vote
0answers
443 views

Complexity of set oprations in algorithm

I am designing a graph algorithm. Some steps of the algorithm, are set operations (union, difference, intersection, set-membership). Can I assume them as $~ \mathcal{O}(1)$ operations? Have someone ...
1
vote
1answer
320 views

Is Maximum Independent Set in coNP

I need to determine whether the following problem $X$ is in coNP: Given a graph $ G=(V,E) $ and a positive integer $s\leq|V| $, is there an independent set that is the largest for $G$ of size at ...
3
votes
2answers
98 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, ...
5
votes
1answer
703 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 ...
14
votes
5answers
992 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, ...
0
votes
1answer
141 views

Number of combinations to put n items into 2 bags [closed]

I’m currently working on a finger exercise for mit6.00.2x, a MOOC in computaional thinking, and was having some issues. First of all: don’t worry, I don’t need you to do my homework for me, I just ...
0
votes
0answers
116 views

Algorithm: How many symbols of occurence k fit into b buckets under condition

I have the following problem to solve: Given a set of buckets $B=\{b_0,\dots b_n\}$ of known size, a constant $k$ < |B| and a set of symbols $S=\{s_0,\dots, s_?\}$ with unknown size. Place ...
1
vote
1answer
852 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 ...
2
votes
1answer
104 views

N songs, M instruments, how to pick K instruments to cover maximal amount of songs

I have $N$ songs, $M$ instruments. Each song requires one or more of the $M$ instruments in order to be played. My $K-1$ friends and I want to learn to play $K$ different instruments, and we want to ...
0
votes
1answer
367 views

“Regular languages over a common alphabet are closed under union.”

I just want to make sure I understand what this means. I am new to Formal Languages and this is my first week of courses. Suppose we have two regular languages, $L_1$ and $L_2$, with a common ...
4
votes
1answer
263 views

Enumerating sets in a random order

I have multiples arrays. I'd like to enumerate all sets containing exactly one item from each array in a (pseudo-)random order, without explicitly building the array of all sets. Any solution, even ...
1
vote
1answer
326 views

Check whether set of strings is prefix-free via lexicographic sort?

I have a set of strings and would like to establish whether the set has the prefix property, which basically means that no string in the set is a prefix of any other string in the set. So ...
1
vote
2answers
229 views

Set notation of the set of all strings

How do I present the complement using set notation? I guess it has to be shows with universal set - {aa,bb} but I do not know how to represent the universal set in ...
1
vote
1answer
82 views

What is an efficient way to calculate the biggest system of disjunct sets?

Let $I$ be a finite set of items and $\mathcal{M} = \{M | M \subseteq I\}$ be a set of subsets of $I$. The task is to find the biggest subset $\tilde{\mathcal{M}} \subseteq \mathcal{M}$ so that all ...
1
vote
1answer
79 views

Many-one reducibility: why $A = \{1\}$ is not a counterexample to $\forall A : A \leq_m A \cup \{0\}$?

I'm looking at a textbook exercise that asks to prove or give a counterexample that $\forall A : A \leq_m A \cup \{0\}$. $A \leq_m B$ is defined as: $\exists f$ total, computable s.t. $\forall x \in ...
2
votes
0answers
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 ...
2
votes
1answer
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 ...
2
votes
2answers
169 views

Efficient immutable data structure for small multi-sets of integer ranges?

Background I'm currently writing some Elixir algorithms that are quite computationally expensive. The most-used datastructure is a multi-set of (finite) integer ranges. Modifying this data structure ...
2
votes
1answer
72 views

Compact, reversible mapping from set partitions of length k to integers

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 $\...