Questions tagged [sets]

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

269 questions
355 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 ...
39 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?
312 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)$...
34 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-...
209 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 ...
85 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 ...
159 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 ...
63 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 ...
69 views

38 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 ...
247 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: ...
41 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 ...
419 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 ...
303 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 ...
84 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, ...
627 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 ...
983 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, ...
132 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 ...
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 ...
767 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 ...
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 ...
342 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 ...
262 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 ...
308 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 ...
184 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 ...
79 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 ...
78 views

67 views

The meaning of “set” in NP-complete problem

Garey and Johnson describe in their book many NP-complete problems which are based on sets, for example Hitting Set, Minimum Test Set, Set Packing, Set Splitting, and many more. The traditional ...
624 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 ...
80 views

What kinds of problems are modeled by a recursive definition of a set of strings?

Given this definition: The set $\Sigma^*$ of strings over the alphabet $\Sigma$ is defined recursively by: BASIS STEP: $\lambda \in \Sigma^*$ (where $\lambda$ is the empty string) RECURSIVE ...
61 views