Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

5
votes
1answer
291 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 ...
25
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 ...
21
votes
9answers
700 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 ...
15
votes
12answers
766 views

Number of surjections

Task Given 2 positive integers n and k, where n > k, output the number of surjections ...
24
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 ...
14
votes
5answers
901 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 ...
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 ...
14
votes
2answers
164 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 ...
8
votes
3answers
557 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 ...
12
votes
5answers
616 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 ...
65
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 ...
30
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 ...
11
votes
4answers
282 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
491 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 ...
28
votes
44answers
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 ...
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, ...
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 ...
10
votes
12answers
311 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, ...
12
votes
3answers
759 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 ...
11
votes
4answers
458 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 ...
10
votes
1answer
258 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 (...
1
vote
1answer
106 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 ...
9
votes
3answers
719 views

Print the intersection of sequences

Sequences You are given four number sequences, numbered 1 through 4. OEIS The location of 0...
8
votes
2answers
901 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
5k 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
6answers
788 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. ...
7
votes
8answers
744 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 ...
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 ∪ ...
5
votes
8answers
963 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 ...
9
votes
3answers
628 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 ...
4
votes
6answers
663 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]. ...