Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [sets]

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

1
vote
1answer
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 ...
1
vote
0answers
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?
3
votes
1answer
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)$...
3
votes
1answer
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-...
0
votes
1answer
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 ...
2
votes
1answer
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 ...
0
votes
1answer
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 ...
2
votes
2answers
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 ...
2
votes
0answers
69 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
100 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
211 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
41 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
24 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
116 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
127 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
128 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
156 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
126 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
112 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
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 ...
1
vote
0answers
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: ...
2
votes
1answer
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 ...
1
vote
0answers
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 ...
1
vote
1answer
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 ...
3
votes
2answers
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, ...
5
votes
1answer
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 ...
14
votes
5answers
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, ...
0
votes
1answer
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 ...
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
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 ...
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
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 ...
4
votes
1answer
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 ...
1
vote
1answer
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 ...
1
vote
2answers
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 ...
1
vote
1answer
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 ...
1
vote
1answer
78 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
34 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
180 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
165 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
70 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 $\...
2
votes
1answer
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 ...
7
votes
2answers
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 ...
2
votes
1answer
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 ...
-1
votes
1answer
61 views

A max-even subset problem

I want to know if there is any polynomial algorithm for the problem, or any NP-completeness result. Given a set $S$ and $m$ subsets $C_1, \dots, C_m$ of $S$, we want to find a non-empty set $X\...
4
votes
3answers
324 views

My algorithm is different from CLRS' — is it wrong?

Exercise 2.3-7 from "Introduction to Algorithms" by Cormen et al. Third Edition, states: Describe a O(n lg n)-time algorithm that, given a set S of n integers and another integer x, determines ...
1
vote
0answers
57 views

Create the shortest list that contains a set of subsets in block

I have a problem where I have a set of subsets and I want to create the shortest list where I can find all subsets in it. Each subset must be a block of that list. The input is a set of set of ...
0
votes
1answer
53 views

Finding top k which are the most different from each other

Assume I have a set of items $A$ and each item $a \in A$ has a score $s(a)$. Also, each two items $a_1,a_2 \in A$ have variety score $var(a_1,a_2)$ which tells how different they are. I want to ...
1
vote
1answer
441 views

Letter Combinations of a Phone Number

I came across this problem in the “Elements of Programming Interviews” interview preparation book, and also on the site, leetcode.com (link to problem). Problem statement – Letter Combinations of a ...
28
votes
5answers
5k views

Boolean search explained

My mother is taking some online course in order to be a librarian of sorts, in this course they cover boolean searches, so they can search databases efficiently, however, she got a question sounding ...