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.

0
votes
2answers
715 views

find the optimal combination [closed]

Suppose I have these values with weights -- $$ x_1 = 2\\ x_2 = 4\\ x_3 = 5\\ $$ There is no negative or $0$ value. I need to find $2$ element subset with maximum value computed from a function $f(\...
2
votes
1answer
359 views

How to apply “verification” and “decision” for the SUBSET SUM problem?

The SUBSET SUM problem states that: Given finite set S of integers, is there a subset whose sum is exactly t? Can someone show me why verification is simpler ...
1
vote
1answer
1k views

Minimize sum of squared error

I have an array of real numbers, I want to partition them into k sets. In each set, I calculate the sum of squared error. Then, I add up all the sum of squared error for all the set. I want to ...
4
votes
1answer
88 views

Count all possible unions in a collection of sets

Say we have a collections of sets $\mathcal X = \{X_1, \dots, X_n\}$ (not necessarily disjoint), and we want to count the number of possible unions of sets in $\mathcal X$, i.e. the size of $\{\...
3
votes
1answer
101 views

Does any one know what this problem is called?

We are given finite sets $A$ and $B$ and a set $S\subseteq \mathcal{P}(A)$. The members of $\mathcal{S}$ may have arbitrary intersections with one another and their union is not necessarily $A$. ...
2
votes
0answers
127 views

Message protocol to probabilistically infer missing object from Union of two subsets of a larger set

This was a challenge problem I read some time ago and just remembered it: Say you have two people, $A$ and $B$, collect objects distinctly labeled $1,...,n$. They will each separately collect sets ...
1
vote
1answer
52 views

Find a collection of sets where each number from a given list is contained in a different set

I have a set of numbers S of cardinality N, and a collection of sets each containing some subset of S. The cardinality of each of these sets can be anywhere from 1 to N. The number of sets is ...
2
votes
1answer
544 views

compressing a set of binary strings with fixed length

I'm looking for a data structure / algorithm to store an unordered set S of binary strings of a fixed length n (i.e. all ...
3
votes
1answer
160 views

How can finite sets be represented as a type?

Manually self-migrated from stack overflow. A set of objects of a type T is often represented using its indicator function (set T = ...
1
vote
1answer
79 views

Online and parallizeable set intersection algorithm

I have problem that is reducible to the following: From a collection of stacks, find all items whose "keys" are on all stacks. My current solution to this problem is to just pop things off as ...
1
vote
0answers
25 views

Given a set of sets and a storage area, find an order that minimizes the sum of the differences between each set and the storage area

This problem is based on an order picking problem with a forward area. The problem description is as follows. We have a warehouse with a set of items $I$ and a forward area $F$ of size $k$. Each day,...
0
votes
1answer
346 views

Find strings in L^4

Let L = {ab,aa,baa}. I need to find L^4. From my understanding, I union the set. So: ...
2
votes
1answer
137 views

Typical set in Shannon's source coding theorem

I was following the textbook by David Mackay: Information theory inference and learning algorithms. I have question on asymptotic equiparition' principle: For an ensemble of $N$ $i.i.d$ random ...
4
votes
1answer
80 views

Communication complexity of comparing sets, for Bitcoin

In Bitcoin, when one node wants to tell another node about a block, it sends the block header, then all the transactions it contains. This is inefficient, because the receiving node might already have ...
1
vote
2answers
128 views

What is the term for this set

I have a set of related data/objects for which, when undergoing some algorithm, there should be only one valid match. Is there a unique term for this type of set? A common practical use case would be ...
3
votes
2answers
2k views

Returning a random subset with length k of N strings while only storing at most k of them

Here's the problem. I've written a program that reads strings from stdin, and returns a random subset of those strings. The only other argument provided to the program is the length of the subset, $k$....
1
vote
1answer
70 views

Is a set system an independence system, if and only if it is an accessible system, and has the Interval Property without Lower Bounds

From Wikipedia, a finite matroid $M$ is defined to be $(E,F)$, where $E$ is a finite set and $F$ is a family of subsets of $E$, so that it satisfies either nonempty, the hereditary property, and ...
6
votes
2answers
525 views

Existence of Efficient Set Difference Algorithm

As a foreword, I'm not asking what the algorithm is, just whether one can possibly exist (though, if it does already exist and someone knows what it is, that'd be great). Basically, given two sets $S$...
1
vote
1answer
124 views

Lower-bounding the Membership Problem in the Bitprobe Model

I am working through the following paper "Data Structures for Storing Small Sets in the Bitprobe Model" by Radhakrishnan et al. and am confused regarding one of their arguments about a lower bound. ...
2
votes
1answer
52 views

Find $k$ subsets containing a particular element quickly

Suppose there are $n$ subsets of $U$. I want to quickly (in terms of average-case) find k $ (< n)$ subsets that contain $e \in U$ (call this Extraction(e)). Elements are integers. To that effect, ...
1
vote
1answer
41 views

Set that keeps unique categories of objects

I would like to know if this type of special set operator exists, and if yes what is it called and if it has any other special properties. Lets say I have this set $S$ of items. Like all sets, if ...
2
votes
1answer
194 views

Maximizing the Sum of a Subset with Excluding pairs

I have a set of nodes S where all the nodes of an arbitrary integer value. I Also have a set of pairs of nodes from S, indicating that those node cannot be in the same subset. Given a subset of S, ...
4
votes
1answer
128 views

What does $\{$ a set $\}^{+}$ mean in the context of languages?

I came across this notation and I don't know the meaning of it, or if it's a typo: $\{$ some set $\}^{+}$ What does the + mean, i.e., the plus operator applied to a set?
2
votes
4answers
371 views

What is the point of (Compactness theorem in the) Overspill principle?

The principle (called a Löwenheim–Skolem theorem by Huth and Ryan) states Let $\phi$ be a sentence of predicate logic such that for any natural number $n \geq 1$, there is a model of $\phi$ with ...
1
vote
3answers
124 views

How do I mathematically express a set generated using two loop variables within a single for loop?

I don't know the proper mathematical expression for for-loops, especially those that carry two distinctly behaving variables with each iteration. For example, assuming ...
5
votes
3answers
223 views

How to enumerate a product set?

I am coding a procedure that takes an integer $d$, and generates $d$ finite lists $X_1 \ldots, X_d$ of elements. I would then like for it to output a list of the elements in the product set $X_1 \...
2
votes
2answers
408 views

Reconstruct directed graph from list of ancestors for each node

I have a problem that I encountered that boils down to the following: Considered this directed graph I found on Google: I have the following information available to me ...
1
vote
1answer
61 views

What is the name two mutually idempotent functions?

To clarify, in haskell, there is an ord function that gives the byte integer of a character (i.e. ord 'a' yields ...
3
votes
1answer
314 views

Asymptotic lower bound on the number of comparisons needed to find the intersection of unsorted arrays

A homework problem in my current CS class asks us to produce a comparison-based procedure for taking (essentially—there are some poorly-specified rules about duplicates) the set intersection of $k$ ...
2
votes
1answer
49 views

Total ordering of sets of fixed size

I'm curious if there is a name for this way of ordering finite sets of natural numbers (shown here for the case 3 elements, but can be extended to any number of them): ...
8
votes
2answers
1k views

Looking for a set implementation with small memory footprint

I am looking for implementation of the set data type. That is, we have to maintain a dynamic subset $S$ (of size $n$) from the universe $U = \{0, 1, 2, 3, \dots , u – 1\}$ of size $u$ with operations ...
4
votes
1answer
404 views

Most common subset of size $k$

I'm trying to write an algorithm that detects the most common subset of at least size $k$, from a collection of sets. If there are ties for the most common subset, I want the one of them whose size ...
1
vote
1answer
111 views

Number of K-sets [closed]

I am having a plane in N dimension. Th distance between 2 points (a1,a2,...,aN) and (b1,b2,...,bN) is max{|a1-b1|, |a2-b2|, ..., |aN-bN|}. I need to to know how many K-sets exist(here K-set refers to ...
2
votes
1answer
176 views

Set packing variant

There are n collections of M sets. Pick a single set from each collection, such that all n picked sets are pairwise disjoint. This problem can be converted to the ...
8
votes
2answers
5k views

Equivalence of independent set and set packing

According to Wikipedia, the Independent Set problem is a special case of the Set Packing problem. But, it seems to me that these problems are equivalent. The Independent Set search problem is: given ...
-1
votes
1answer
814 views

Finding number of maximum independent sets in tree, using dynamic programming

I'm quite stuck trying to answer this. The problem of finding the size of the maximum independent set in a tree using dynamic programming is well documented and many solutions are around. I've been ...
3
votes
1answer
437 views

Is the set-partition problem polynomial time reducible to the subset-sum problem?

There are many solutions on the web showing that the subset-sum problem is polynomial time reducible to the set-partition problem. However, during my search, I came across the following powerpoint ...
3
votes
1answer
1k views

Is the image of a function the codomain of a function?

Here is a definition from the functions section in my discrete math textbook (Discrete Mathematics and its Applications 7e, Rosen 2012): Let $f$ be a function from $A$ to $B$, and let $S$ be a ...
13
votes
4answers
9k views

Computing set difference between two large sets

I have two large sets of integers $A$ and $B$. Each set has about a million entries, and each entry is a positive integer that is at most 10 digits long. What is the best algorithm to compute $A\...
3
votes
1answer
6k views

Is every subset of a decidable set, also decidable?

Is it true that if A is a subset of B, and B is decidable, than A is guaranteed to be decidable? I believe it would be true because all the subsets of B should also be decidable making A decidable. I'...
6
votes
2answers
1k views

Concatenation of the intersection of two languages

I'm enrolled to a Formal Language And Automata course, and we have to prove this equation on sets of strings: $$(L_1\cap L_2)\cdot L_3 ≠ (L_1\cdot L_3) \cap (L_2\cdot L_3)$$ I've tried a lot of sets ...
0
votes
1answer
50 views

Prove that $|P(X)| = 2^{|X|}$ [closed]

Prove that for any finite set $X$, $|P(X)| = 2^{|X|}$. The solution should use induction.
2
votes
1answer
48 views

Finding users covering a set x by x

I have a Set $S$ of objects, a set $U$ of users and a map $c: U \rightarrow S^{\prime}$, where $S^{\prime} \subset S$ and $\emptyset \notin S^{\prime}$. Every time I add a new entry to $c$, i.e. ...
2
votes
1answer
112 views

Enumerating all set covers when knowing one set at least

I have an index taking as keys values from the power set $P(S)$ of a set $S$, except for $\emptyset$ and $S$. Then I have a query $Q=(s, k)$, where $s \in P(S) - \{\emptyset \cup S\}$ and $ 1 < k \...
6
votes
1answer
161 views

Name for concept: each pair of sets is either nested or disjoint

Does this property have a name? Given a collection of sets $\mathcal{P}$, for all pairs $A, B\in\mathcal{P}$, either $A\cap B=\emptyset$ or $A\subseteq B$ or $B\subseteq A$. This concept could ...
2
votes
1answer
708 views

Set combination data structure (And storage complexity)

I have already posted this question on Stackoverflow, but I'm starting to think that this is the right place. I have a problem where I am required to associate unique combinations from a set (unique ...
0
votes
1answer
258 views

Is there a formula to state the number of 'sets' of 'ordered sets within ordered groups'?

I am new to this and an amateur... please help. My Question in practical terms: Given The three following inputs... determine the number of unique group arrangements as an ordered set. INPUT: 'a' = ...
0
votes
2answers
102 views

Computing every possible sum of integers taken from different sets

I'm trying to proove $NP$-membership for a problem from the following certificate. I have $n$ sets of integers : $$(S_i)_{i \in \{1,\dots,n\}}$$ Each set has a number $m_i$ of integers. I make "...
-2
votes
1answer
307 views

Subset product problems (one “easy” one “difficult”)

This question is from an exam preparation that I have to demonstrate to my teacher to show him that I understood the topic thoroughly . Given a set $S$ of integers with $n$ elements, an integer $z$ ...
3
votes
1answer
78 views

Find all items which are subsets of an item

I have a problem that I think should have been studied. I am looking for algorithms for it. Each item is a set of key-value pairs. Let $x$ be an item and $F$ be a set of items. Each key and each ...