Questions tagged [set-theory]
Set theory is the branch of mathematics that studies unordered collections of objects. Challenges with this tag will involve the manipulation or analysis of sets.
45
questions
17
votes
15
answers
1k
views
Reconstruct a list of strings from its prefixes
emanresu A posted a challenge to reconstruct an ordered list of integers from its unordered set of unordered prefixes. Many users (beginning with xnor's answer) noticed that summing each unordered ...
- 15.8k
18
votes
18
answers
1k
views
Reconstruct a list from its prefixes
A list \$[a_1,a_2,a_3 \cdots a_n]\$ can be uniquely represented as an unordered list of its prefixes - \$ [[a_1],[a_1, a_2], [a_1,a_2,a_3] \cdots [a_1,a_2,a_3 \cdots a_n]] \$. This can be in any order ...
- 39.2k
17
votes
35
answers
3k
views
The Jaccard Index
The Jaccard index / similarity coefficient, also known as the Tanimoto index / coefficient, is a statistic used for gauging the similarity and diversity of finite sample sets. It was developed by ...
- 1,597
17
votes
15
answers
1k
views
Enumerate all pure sets
In set theory, a set is an unordered group of unique elements. A pure set is either the empty set \$\{\}\$ or a set containing only pure sets, like \$\{\{\},\{\{\}\}\}\$.
Your challenge is to write a ...
- 39.2k
23
votes
18
answers
2k
views
Print the power set of the power set ... of an empty set
Given a non-negative integer n, print the result of P(P(...P({}))), where the number of P's ...
- 341
15
votes
12
answers
711
views
Only one from each set
Your input is a non-empty set of non-empty sets of positive integers. For example:
{{1}, {2, 3}, {2,4}, {1,4}}
Your task is to output the maximal number of ...
- 7,898
9
votes
7
answers
508
views
Distinct Subset Sums: Extending A276661
Consider the integer set \$S = \{3, 5, 6, 7\}\$. If we list all \$2^n\$ subsets of \$S\$ (its powerset) and calculate their sums, we get
$$
\mathcal{P}(S) = \{\emptyset, \{3\}, \{5\}, \{6\}, \{7\}, \{...
- 50.1k
10
votes
4
answers
305
views
Venn of \$n\$ statements
Given a positive integer \$n\$, output \$n\$ 2D bool images with the same width and height such that:
Each image should be 4-connected, i.e. for each two pixels that are true, you can start from one ...
- 25k
2
votes
0
answers
140
views
Compute the minimal and maximal subset of a set of sets [closed]
Let S be a set of sets, for example S = {{A},{B},{A,B}}. A maximal subset, Max, is an element of S such that no other set in S ...
- 29
13
votes
25
answers
3k
views
N-Dimensional Cartesian Product
Introduction
The Cartesian product of two lists is calculated by iterating over every element in the first and second list and outputting points. This is not a very good definition, so here are some ...
- 2,203
6
votes
2
answers
602
views
Surreal Numbers
Surreal Numbers are one way of describing numbers using sets. In this challenge you will determine the value of a surreal number.
Intro
A surreal number consists of two sets: a left and right. The ...
- 2,869
27
votes
12
answers
2k
views
Does this Set Represent a Natural Number?
In set theory, the natural numbers \$\mathbb{N} = \{0, 1, 2, 3, ...\}\$ are usually encoded as pure sets, that is sets which only contain the empty set or other sets that are pure. However, not all ...
- 26.2k
20
votes
9
answers
829
views
Compute the superset
Your task here is simple:
Given a list of integer sets, find the set union. In other words, find the shortest list of integer sets that contain all the elements in the original list of sets (but no ...
- 14.5k
16
votes
12
answers
911
views
Number of surjections
Task
Given 2 positive integers n and k, where n > k, output the number of surjections ...
- 49.9k
26
votes
9
answers
1k
views
Verify Topology
Challenge
Given a set T of subsets of a finite set S={1,2,3,...,n}, determine whether T is a ...
- 43.9k