# Questions tagged [sets]

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

348 questions
Filter by
Sorted by
Tagged with
6k views

### How to prove a set has infinite cardinality?

Set S is a set consisting of all string of one or more a or b such as "a, b, ab, ba, abb, bba..." and how to prove set S is a infinity set. I have tried proving set S as one to one corresponding to ...
890 views

### Algorithm for generating coprime number sequences?

Does anyone know of an algorithm to generate a set of numbers of size $N$ which are all co-prime to eachother? Ideally I'm looking for something that has random access abilities so i could ask for ...
822 views

698 views

### Application of set theory subjects as ordinals, forcing, generic filters in software engineering

I am going to teach a course in set theory for software engineering students. I am going to talk in this course about: ordinal numbers, partial orders, well ordering, generic filters and maybe some ...
391 views

105 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 ...
56 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 ...
627 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 ...
236 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 = ...
88 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,...
738 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: ...
158 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 ...
90 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 ...
837 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$...
133 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. ...
### 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, ...
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 ...