# Questions tagged [sets]

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

329 questions
Filter by
Sorted by
Tagged with
28 views

### Assistance with Notation in the Paper Entitled: “Search Through Systematic Set Enumeration”

So I'm reading "Search Through Systematic Set Enumeration" by Ron Rymon (currently available online for free. I'm having a problem with the notation in the following definition presented ...
653 views

37 views

70 views

### Tradoff between space and false positive rate when using bloom filters

Bloom Filters have false positive rate of $\epsilon = 2^{-k}$ with a data structure of size $m = n\log (\frac{1}{\epsilon})\ln 2$. Suppose you fix the number of hash functions at $k \le 3$. What is ...
1k views

104 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$. ...
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 ...
55 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 ...
577 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 ...
210 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 = ...
83 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 ...
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,...
564 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: ...
150 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 ...
86 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 ...
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 ...
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$....
75 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 ...
746 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$...
129 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. ...
53 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, ...
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 ...
197 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, ...
133 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?
421 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 ...
137 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 ...