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.
35
questions
11
votes
23answers
2k 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 ...
25
votes
8answers
1k views
Verify Topology
Challenge
Given a set T of subsets of a finite set S={1,2,3,...,n}, determine whether T is ...
6
votes
11answers
1k views
Sum of Products of Subsets
Given an integer k and a list of integers A of size n, find the product of all subsets in A of size k and sum them together.
For example,
k = 2
n = 4
A = 1 2 3 4
...
4
votes
6answers
686 views
Write a program to perform set operations.
Your task is to write a program to perform set operations. The operations and arguments are taken from command line in the format program operation [argument]. ...
9
votes
17answers
862 views
set intersection of two lists
Your goal is to compute the set intersection of two lists of integers. The intersection is defined as the unique un-ordered group of integers found at least once in both input list.
Input
The input ...
28
votes
47answers
3k views
As Easy As A-B-C
Input
A string that contains at most one of each of the letters A, B, and C. They may be in ...
5
votes
1answer
322 views
Surreal Numbers
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 ...
27
votes
22answers
1k views
Natural construction
The natural numbers including 0 are formally defined as sets, in the following way:
Number 0 is defined as the empty set, {}
For n ≥ 0, number n+1 is defined as n ∪ {n}.
As a consequence, n = {0, 1, ...
26
votes
11answers
1k 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 ...
20
votes
9answers
709 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 ...
32
votes
34answers
3k views
Is it a sum-free set?
A set is sum-free if no two (not necessarily distinct) elements when added together are part of the set itself.
For example, {1, 5, 7} is sum-free, because all ...
12
votes
34answers
2k views
Cartesian product of two lists
Task
Given two lists of characters, output their Cartesian product, i.e. the list of pairings of each letter from the first list with each letter from the second list.
Example
...
16
votes
12answers
789 views
Number of surjections
Task
Given 2 positive integers n and k, where n > k, output the number of surjections ...
10
votes
12answers
316 views
N-uniquely additive sets
Remember that a set is unordered without duplicates.
Definition An N-uniquely additive set S whose length is K is a set such that all N-length subsets in S sum to different numbers. In other words, ...
7
votes
8answers
749 views
Operations on Sets
Note: I have accepted an answer, but I'm willing to accept a better answer if it comes.
Write a program that computes operations on sets. You may take input either from standard input or from command ...
31
votes
18answers
1k views
Uniquify Identifiers
Introduction
By definition, unique identifiers should be unique. Having multiple identifiers that are the same causes one to retrieve unexpected data. But with data arriving concurrently from ...
8
votes
3answers
676 views
ASCII-Art Venn Diagram
Given two lists that contain no duplicate elements a and b, find the crossover between the two lists and output an ASCII-Art ...
14
votes
5answers
909 views
Golf a bijection within the natural numbers which map the primes to a proper subset of the primes
Definitions
A bijection from a set S to a set T is a function from S to ...
14
votes
2answers
165 views
Find Subset Factors
Let's imagine we have a finite set of positive integers. This set can be represented as a line of dots where each integer present in the set is filled in like a scantron or punch card. For example ...
12
votes
5answers
668 views
Venn Diagram Cells
Given multiple sets, e.g. s1={2,3,7}, s2={1,2,4,7,8} and s3={4,7}, a Venn diagram visualizes ...
66
votes
5answers
5k views
Powerprogramming: O(1^N), O(N^1), O(2^N), O(N^2) all in one
Write a program (or function) that exhibits four common big O time complexities depending on how it is run. In any form it takes in a positive integer N which you may assume is less than 231.
When ...
10
votes
4answers
285 views
Greedily partition the list of combinations with repetition
First, a few definitions:
Given n and k, consider the sorted list of multisets, where for each multiset we choose ...
17
votes
23answers
2k views
Construct the natural numbers with sets
This construction is a way of representing the Natural Numbers.
In this representation, 0 is defined as the empty set and for all other numbers, n is the union of {0} and {n-1}.
For example to ...
14
votes
4answers
496 views
Solve Math Problem Notation
Imagine I have an infinite number of homework problems (!) each given an integer number.
Math Problem Notation is a notation for describing subsets of the problem using problem specifiers.
An MPN ...
11
votes
4answers
462 views
Map a list of indefinite size to a number!
It is well known, in the field of Mathematics studying infinity, that the Cartesian product of any finite amount of countable sets is also countable.
Your task is to write two programs to implement ...
9
votes
6answers
802 views
Permutation Numbering
The Challenge
For a given set of n integers, write a program which will output its lexicographic index.
The Rules
The input must only be a set of unique non-negative integers separated by spaces.
...
12
votes
3answers
803 views
Laver table computations and an algorithm that is not known to terminate in ZFC
The Laver tables provide examples of programs which have not been shown to terminate in the standard axiomatic system of mathematics ZFC but which do terminate when one assumes very large cardinal ...
9
votes
3answers
735 views
Print the intersection of sequences
Sequences
You are given four number sequences, numbered 1 through 4.
OEIS The location of 0...
10
votes
1answer
260 views
Set Theoretic Arithmetic (+ and *) [closed]
Set Theoretic Arithmetic
Premise
There have been a couple challenges already that involve multiplying without the multiplication operator ( here and here ) and this challenge is in the same vein (...
20
votes
21answers
2k views
Length of String Using Set Theory
From Wikipedia Set-theoretic definition of natural numbers
The set N of natural numbers is defined as the smallest set containing
0 and closed under the successor function S defined by S(n) = n ∪ ...
1
vote
1answer
107 views
Pythy Finite Ordinals [duplicate]
Write a program in any language that takes a single natural number n as input and generates a Pyth program that, in turn, produces, using nested lists, the nested set given by S(n), where:
S(0) = ∅
...
14
votes
2answers
256 views
Maximally extend integer intervals
Suppose you are given a set of non-intersecting intervals of integers [a1,b1],[a2,b2],[a3,b3],...,[aN,bN]. (Where [a,b] is the ...
8
votes
2answers
909 views
¿Yo Quiero jQuery?
The Setup
You are given a simple web page with 11 elements:
10 input elements with IDs i1 thru ...
26
votes
9answers
6k views
Golf a Venn Diagram generator
Golf a Venn Diagram generator
In order to properly celebrate John Venn's 180th birthday, today your task will be creating a program that outputs a Venn Diagram!
Input:
A positive integer ...
9
votes
3answers
630 views
Calculate the number of topologies on {1,2,…,n}
Task
Write a function/program which takes n as a parameter/input and prints/returns the number of topologies (which is demonstrated below) on the set ...
