Tagged Questions

The tag has no wiki summary.

learn more… | top users | synonyms

1
vote
1answer
19 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
84 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
0answers
18 views

Where can I get a good tutorial or book on Discrete Math? [on hold]

I'm currently taking a course at school on Discrete Math and the experience has been terrible, my lecturer isn't even helping matters, we've only had 3 classes this semester and exams are coming up in ...
3
votes
1answer
37 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
20 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
20 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 ...
0
votes
1answer
37 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
23 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
37 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
116 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
327 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, ...
1
vote
1answer
24 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 ...
4
votes
2answers
73 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 ...
2
votes
1answer
58 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
37 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
25 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
50 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
81 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
3answers
211 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 ...
0
votes
3answers
56 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 ...
4
votes
3answers
83 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
58 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
20 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
151 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
29 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): ...
6
votes
2answers
193 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 ...
3
votes
1answer
105 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
88 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
52 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 ...
4
votes
2answers
238 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
107 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
196 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
86 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 ...
7
votes
4answers
455 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 ...
-1
votes
1answer
563 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. ...
5
votes
2answers
152 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
34 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
29 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
52 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 ...
5
votes
1answer
116 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
155 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
92 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
83 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
138 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$ ...
1
vote
1answer
58 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 ...
5
votes
0answers
81 views

Overlap Maximization problem

Here's the problem: I have a collection of collections, $C$, where each $c\in C$ is a collection of sets $X\subset U$. Denote $c_i$ as the i-th $X$ in $c$. Informally, I want to map all the sets in ...
1
vote
1answer
203 views

If $L = L(M)$ then $L$ is a subset of $L(M)$ and $L(M)$ is a subset of $L$

If $L = L(M)$ then $L$ is a subset of $L(M)$ and $L(M)$ is a subset of $L$. Can anyone clarify what does this mean?
8
votes
4answers
922 views

Data Structure for Set Intersection?

Is there any data structure that maintain a collection of set (of finite ground set) supporting the following operations? Any sublinear running time will be appreciated? Init an empty set. Add an ...
5
votes
1answer
200 views

What is a compact way to represent a partition of a set?

There exist efficient data structures for representing set partitions. These data structures have good time complexities for operations like Union and Find, but they are not particularly ...
6
votes
2answers
115 views

Test if there are two subsets which cover a set

Given a set $S$ of $n$ elements, and a set $\mathcal{X}$ of $m$ subsets of $S$, decide if there exist $U,V \in \mathcal{X}$, s.t. $U \cup V = S$. Brute force would take time $O(nm^2)$ but is there ...