# Questions tagged [sets]

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

330 questions
Filter by
Sorted by
Tagged with
106 views

47 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$...
47 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 ...
909 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 ...
488 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 ...
49 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?
341 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)$...
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-...
421 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 ...
123 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 ...
353 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 ...
70 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 ...
70 views

66 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 ...
717 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: ...
45 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 ...
546 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 ...
382 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 ...
126 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, ...
1k 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 ...
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, ...
193 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 a total ...
1k 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 ...
107 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 ...
549 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 ...
265 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 ...
367 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 ...
313 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 ...
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 ...