Bijection between natural numbers and finite sets

−0

Definitions

A natural number is either zero, or a successor of some other natural number.

A set is an unordered collection of zero or more elements. Each element is a set. Two sets that have same elements are equal. In this challenge we consider only hereditarily finite sets.

Cardinality of a set is the number of distinct elements of the set. For any set x, it is represented as |x|.

A set can be represented as a string by encapsulating space-separated string representations of its elements into curly braces. For example, {} is the empty set, {{}} is the set that contains only the empty set, {{}, {}} is still the set that contains only the empty set, {{}, {{}}} is the set that contains only the empty set and the set that contains only the empty set. Duplicate elements are ignored. The order of elements is not important.

Binary relation < on sets is defined in the following way. Given two sets A and B. If A is equal to B, then neither A < B nor B < A. If A is not equal to B, then let m = |A| and n = |B|. If m < n then A < B and if n < m then B < A (where < is the well-known binary relation on natural numbers). If m = n then let x be the array of distinct elements of A sorted in ascending order (for each two elements p and q in the array, p < q iff p precedes q) and let y be the array of distinct elements of B sorted in ascending order. Let i be the smallest index in the array such that the corresponding elements in x and y are not equal. The result of A < B is equal to the result of comparison of the corresponding elements with index i from x and y respectively.

Normalized string representation of a set is a string representation of the set such that each element appears only once, elements are sorted in ascending order and the string representation of each element is normalized.

Conversion from a natural number to a set

Let $S$ be the class of all hereditarily finite sets and let $\Bbb N$ be the set of all natural numbers. The conversion from a natural number to a set is denoted by function $f:\Bbb N\to S$. The conversion from a set to a natural number is denoted by function $g:S\to\Bbb N$. Since it is a bijection, $f(x) = g^{-1}(x)$ and $f^{-1}(x)=g(x)$.

We describe the function $f$. Given a natural number n. Let s be the string {. Perform these steps iteratively (in each iteration apply the first step that can be applied):

If there is only one unmatched { in s and n is 0, then append } to s, interpret s as a set and return it as the result.
If there is only one unmatched { in s and n is not 0, then append { or ,{ (depending on whether the previous character was { or } respectively) and decrement n by 1.
If appending } to s would violate the normalized string representation definition, then append { or ,{ to s.
If n is even, then divide it by 2 and append } to s.
If n is odd, then subtract 1, divide it by 2 and append { or ,{ to s.

Function $g$ (the conversion from a set to a natural number) is the inverse of this algorithm.

Task

The task is to implement two functionalities (either in the same program, or two separate programs): one for conversion from natural numbers to normalized string representations of sets and the other for conversion from string representations (not necessarily normalized) of sets to natural numbers.

If your solution consists of two programs (or functions), the total byte count is the sum of byte counts of each program. You are also allowed to have a common header/footer for both programs and in that case the total byte count includes header and/or footer only once.

Input

Input is a string that either represents a natural number in base 10, or a string representation of a set.

Output

If the input is a natural number, then output the normalized string representation of the set corresponding to that number. If the input is a string representation of a set, then output the natural number corresponding to that set.

Spaces after commas are optional both in the input and in the output. That is, you may assume that the input contains spaces or you may assume that the input does not contain spaces (mention your decision in the answer). Similarly, the output that your program produces may or may not contain spaces.

Test cases

Number → Set

0   → {}
1   → {{}}
2   → {{{}}}
3   → {{}, {{}}}
4   → {{{{}}}}
5   → {{}, {{{}}}}
6   → {{{}, {{}}}}
7   → {{}, {{}, {{}}}}
8   → {{{{{}}}}}
9   → {{}, {{{{}}}}}
10  → {{{}}, {{}, {{}}}}
11  → {{}, {{}}, {{}, {{}}}}
12  → {{{{}, {{}}}}}
13  → {{}, {{{}, {{}}}}}
14  → {{{}, {{{}}}}}
15  → {{}, {{}, {{{}}}}}
16  → {{{{{{}}}}}}
17  → {{}, {{{{{}}}}}}
18  → {{{}}, {{{}}}}
19  → {{}, {{}}, {{{}}}}
20  → {{{{}}, {{}, {{}}}}}
21  → {{}, {{{}}, {{}, {{}}}}}
22  → {{{}, {{}, {{}}}}}
23  → {{}, {{}, {{}, {{}}}}}
24  → {{{{{}, {{}}}}}}
25  → {{}, {{{{}, {{}}}}}}
26  → {{{}}, {{}, {{{}}}}}
27  → {{}, {{}}, {{}, {{{}}}}}
28  → {{{{}, {{{}}}}}}
29  → {{}, {{{}, {{{}}}}}}
30  → {{{}, {{{{}}}}}}
31  → {{}, {{}, {{{{}}}}}}
32  → {{{{{{{}}}}}}}
33  → {{}, {{{{{{}}}}}}}
34  → {{{}}, {{{{}}}}}
35  → {{}, {{}}, {{{{}}}}}
36  → {{{{}}}, {{}, {{}}}}
37  → {{}, {{{}}}, {{}, {{}}}}
38  → {{{}, {{}}, {{}, {{}}}}}
39  → {{}, {{}, {{}}, {{}, {{}}}}}
40  → {{{{{}}, {{}, {{}}}}}}
41  → {{}, {{{{}}, {{}, {{}}}}}}
42  → {{{}}, {{}, {{}, {{}}}}}
43  → {{}, {{}}, {{}, {{}, {{}}}}}
44  → {{{{}, {{}, {{}}}}}}
45  → {{}, {{{}, {{}, {{}}}}}}
46  → {{{}, {{{}, {{}}}}}}
47  → {{}, {{}, {{{}, {{}}}}}}
48  → {{{{{{}, {{}}}}}}}
49  → {{}, {{{{{}, {{}}}}}}}
50  → {{{}}, {{{}, {{}}}}}
51  → {{}, {{}}, {{{}, {{}}}}}
52  → {{{{}}, {{{}}}}}
53  → {{}, {{{}}, {{{}}}}}
54  → {{{}, {{}, {{{}}}}}}
55  → {{}, {{}, {{}, {{{}}}}}}
56  → {{{{{}, {{{}}}}}}}
57  → {{}, {{{{}, {{{}}}}}}}
58  → {{{}}, {{}, {{{{}}}}}}
59  → {{}, {{}}, {{}, {{{{}}}}}}
60  → {{{{}, {{{{}}}}}}}
61  → {{}, {{{}, {{{{}}}}}}}
62  → {{{}, {{{{{}}}}}}}
63  → {{}, {{}, {{{{{}}}}}}}
64  → {{{{{{{{}}}}}}}}
65  → {{}, {{{{{{{}}}}}}}}
66  → {{{}}, {{{{{}}}}}}
67  → {{}, {{}}, {{{{{}}}}}}
68  → {{{{}}}, {{{}}, {{}, {{}}}}}
69  → {{}, {{{}}}, {{{}}, {{}, {{}}}}}
70  → {{{}, {{}}}, {{}, {{}}, {{}, {{}}}}}
71  → {{}, {{}, {{}}}, {{}, {{}}, {{}, {{}}}}}
72  → {{{{{}}}, {{}, {{}}}}}
73  → {{}, {{{{}}}, {{}, {{}}}}}
74  → {{{}}, {{}, {{}}, {{}, {{}}}}}
75  → {{}, {{}}, {{}, {{}}, {{}, {{}}}}}
76  → {{{{}, {{}}, {{}, {{}}}}}}
77  → {{}, {{{}, {{}}, {{}, {{}}}}}}
78  → {{{}, {{{}}, {{}, {{}}}}}}
79  → {{}, {{}, {{{}}, {{}, {{}}}}}}
80  → {{{{{{}}, {{}, {{}}}}}}}
81  → {{}, {{{{{}}, {{}, {{}}}}}}}
82  → {{{}}, {{{}}, {{}, {{}}}}}
83  → {{}, {{}}, {{{}}, {{}, {{}}}}}
84  → {{{{}}, {{}, {{{}}}}}}
85  → {{}, {{{}}, {{}, {{{}}}}}}
86  → {{{}, {{}, {{}, {{}}}}}}
87  → {{}, {{}, {{}, {{}, {{}}}}}}
88  → {{{{{}, {{}, {{}}}}}}}
89  → {{}, {{{{}, {{}, {{}}}}}}}
90  → {{{}}, {{}, {{{}, {{}}}}}}
91  → {{}, {{}}, {{}, {{{}, {{}}}}}}
92  → {{{{}, {{{}, {{}}}}}}}
93  → {{}, {{{}, {{{}, {{}}}}}}}
94  → {{{}, {{{{}, {{}}}}}}}
95  → {{}, {{}, {{{{}, {{}}}}}}}
96  → {{{{{{{}, {{}}}}}}}}
97  → {{}, {{{{{{}, {{}}}}}}}}
98  → {{{}}, {{{{}, {{}}}}}}
99  → {{}, {{}}, {{{{}, {{}}}}}}
100 → {{{{}}}, {{}, {{{}}}}}

Set → Number

{} → 0
{{}} → 1
{{}, {}} → 1
{{}, {}, {}} → 1
{{}, {}, {}, {}} → 1
{{}, {}, {}, {}, {}} → 1
{{}, {}, {}, {}, {}, {}} → 1
{{{}}} → 2
{{{}, {}}} → 2
{{{}}, {{}}} → 2
{{{}, {}, {}}} → 2
{{{}, {}}, {{}}} → 2
{{{}, {}, {}}, {{}}} → 2
{{{}, {}, {}, {}}, {{}}} → 2
{{{}}, {}} → 3
{{}, {{}}} → 3
{{{}, {}}, {}} → 3
{{{}}, {}, {}} → 3
{{}, {{}, {}}} → 3
{{}, {{}}, {}} → 3
{{}, {}, {{}}} → 3
{{{}, {}, {}}, {}} → 3
{{{}, {}}, {}, {}} → 3
{{}, {{}, {}, {}}} → 3
{{}, {{}, {}}, {}} → 3
{{}, {{}}, {}, {}} → 3
{{}, {}, {{}, {}}} → 3
{{}, {}, {{}}, {}} → 3
{{{}, {}}, {{}}, {}} → 3
{{{}}, {{}}, {}, {}} → 3
{{{}}, {}, {{}, {}}} → 3
{{}, {{}}, {{}, {}}} → 3
{{}, {}, {{}}, {{}}} → 3
{{}, {}, {}, {}, {}, {{}, {}}} → 3
{{{{}}}} → 4
{{{{}, {}}}} → 4
{{{{}}, {{}}}} → 4
{{{{}, {}, {}}}} → 4
{{{{}}, {{}, {}}}} → 4
{{{{}}, {{}, {}, {}}}} → 4
{{{{}, {}, {}, {}, {}}}, {{{}}}} → 4
{{{{}}}, {}} → 5
{{}, {{{}}}} → 5
{{}, {{{}, {}}}} → 5
{{}, {}, {{{}}}} → 5
{{{{}}, {{}}}, {}} → 5
{{}, {{{}}, {{}}}} → 5
{{{{}}}, {{{}}}, {}} → 5
{{}, {}, {{{}}}, {}} → 5
{{}, {}, {}, {{{}}}} → 5
{{}, {{{}, {}, {}, {}}}} → 5
{{}, {}, {{{}}}, {}, {}} → 5
{{{{}}, {}}} → 6
{{{}, {{}}}} → 6
{{{}, {{}, {}}}} → 6
{{{}, {{}}, {}}} → 6
{{{{}, {}, {}}, {}}} → 6
{{{{}}, {}, {{}}, {}}} → 6
{{}, {{}, {{}}}} → 7
{{}, {{{}}, {}, {}}, {}} → 7
{{}, {}, {{}, {{}, {}}}} → 7
{{{{}}, {}}, {}, {}, {}, {}} → 7
{{}, {}, {{{}, {}}, {{}}, {}}} → 7
{{{{{}}}}} → 8
{{}, {{{{}}}}} → 9
{{{}, {{}}}, {{}}} → 10
{{{}}, {{{}}, {}}} → 10
{{{}, {}}, {{{}}, {}}, {{}}} → 10
{{{}, {{}}}, {{}}, {}} → 11
{{{}, {{}}}, {}, {}, {}, {{}}} → 11
{{{}}, {{}, {{}}, {}, {}}, {}} → 11
{{}, {{}}, {{}, {{}, {}}}, {{}}} → 11
{{{{{}}, {}}}} → 12
{{{{}, {{}}}}} → 12
{{{{}, {}, {{}}}}} → 12
{{}, {{{{}}, {}}}} → 13
{{{}, {{{}}}}} → 14
{{{{{}}}, {}, {}}} → 14
{{{{{{}}}}}} → 16
{{{{{{}}}}}, {}} → 17
{{}, {{{{{}}}}}} → 17
{{{}}, {{{}}}} → 18
{{{}}, {}, {{{}}}} → 19
{{{{}}}, {}, {}, {{}}, {}} → 19
{{{}, {}, {{}, {{}, {}}, {}, {}}, {}, {}}} → 22
{{}, {{{{}}, {}}, {}}} → 23
{{{{{{}}, {}}}}} → 24
{{{{{{}}, {{}, {}}, {}, {}}}}} → 24
{{}, {{{}, {{{}}, {{}, {}}}}}} → 29
{{{{}, {{}, {{}}}}}} → 44
{{{{{}}, {}}}, {{}, {}}} → 50
{{{{}}, {{{}}}}} → 52
{{{}, {{{{}}, {}}, {}}, {}}} → 86
{{{}, {{{}}}, {{}}}} → 102
{{{{{}}, {{{}, {}}}}}} → 104
{{{{{}, {{{{}}}}}}}} → 120
{{{}}, {{{{{{}}, {}}}}}, {}} → 195
{{{}}, {{{}, {}, {}}, {{{}}}, {}}} → 202
{{{}, {{{{{{{{}, {}}}}, {{}}}}}}}} → 3710
{{{{{}}, {}, {{{}}, {{{}}}, {{}}}}, {{}}}} → 13076

Scoring

The shortest program in each language wins.

Clarifications

The challenge is to implement two programs (or functions). The first program takes a base-10 string representation of a natural number as argument and outputs the normalized string representation of the corresponding set. The second function takes a string representation of a set as argument and returns the base-10 string representation of the corresponding natural number. Your programs take a string as an input and produce a string as the output. Each natural number can be uniquely represented as a string, but that is not the case with sets. As we showed, a string representation of a set may contain duplicate elements and the order of elements may vary. That is why we introduce the normalized string representation - to represent a set in a unique way.
Functions $f$ and $g$ are described in the section "Conversion from a natural number to a set". The algorithm that is explained there is for converting from natural numbers to sets, so that represents function $f$. Since it is a bijection, we can uniquely implement function $g$ that does the opposite - converts a set to a natural number. Once again, the algorithm that is explained represents function $f$ and you need to figure out the algorithm for $g$ (it has been proven to exist).
Variable s that is used in the algorithm for explaining function $f$ is just a local variable. It is not explicitly stated that it is related to the normalized string representation of the resulting set that your program should output. Since the definition of $f$ states that $f$ takes a natural number and returns a set, it does not return a string. However, it can be proved that the s from that algorithm is indeed the valid normalized string representation of the resulting set that $f$ constructs. Noticing that s already contains the required final string output is not mandatory for solving the challenge, but can save you some bytes (instead of parsing s and then stringifying it again using normalized string representation, you can just return s). Once again, this is just an optimization detail that is not intended to be explicitly stated in the challenge, but now mentioning it according to the comments.
Your program for converting from natural numbers to sets takes a string as argument (in case of a function), or reads from stdin or in any other way you like. The string represents a natural number in base 10. Your program uses the definition of function $f$ as described above to output the normalized string representation of the corresponding set.
Your program for converting from sets to natural numbers takes a string as argument (in case of a function), or reads from stdin or in any other way you like. The string represents a set (you may expect a non-normalized string as input). Your program uses the definition of function $g$ as described above to output the corresponding natural number stringified in base 10.
The binary relation < on sets that is defined above is not related to the < binary relation on natural numbers. In other words, for any two natural numbers $x$ and $y$, statements $x < y$, and $f(x) < f(y)$ and $\{f(x)\} < \{f(y)\}$ are unrelated. That is, $x < y$ does not imply that $f(x) < f(y)$, and $f(x) < f(y)$ does not imply that $\{f(x)\} < \{f(y)\}$, or any other relation. You should not implicitly assume any relation that is not explicitly stated in this article, or that cannot be concluded from the definitions given here. If you look at the test cases, you can clearly see for example that $f(4) < f(3)$, despite the fact that $3 < 4$.

posted almost 4 years ago

CC0

4y ago

Hakerh400‭

1591 reputation 4 55 164 63

Raw

Markdown

History

1 comment thread

General comments (17 comments)

Communities