# 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 this, one to map from list to integer, one to map from integer to list.

Your function must be bijective and deterministic, meaning that 1 will always map to a certain list, and 2 will always map to another certain list, etc...

Earlier, we mapped integers to a list consisting only of 0 and 1.

However, now the list will consist of non-negative numbers.

# Specs

• Program/function, reasonable input/output format.
• Whether the mapped integers start from 1 or starts from 0 is your choice, meaning that 0 doesn't have to (but may) map to anything.
• The empty array [] must be encoded.
• Input/output may be in any base.
• Sharing code between the two functions is allowed.

# Scoring

This is . Lowest score wins.

Score is the sum of lengths (in bytes) of the two programs/functions.

• "However, now the list will consist of non-negative numbers." May 1 '16 at 5:53
• So, to be clear, we're mapping N^inf -> N?
– user45941
May 1 '16 at 5:56
• @Mego N^inf is not countable. N^k where k is any finite number is. May 1 '16 at 5:57
• Whether it starts from 1 or starts from 0 is your choice. Does that apply to the single integer and to the integers in the list. May 1 '16 at 5:59

# Jelly, 18 16 bytes

### List to integer, 10 8 bytes

TṪạL;³ÆẸ


Maps lists of non-negative integers to positive integers. Try it online!

### Integer to list, 8 bytes

ÆE©Ḣ0ẋ®;


Maps positive integers to lists of non-negative integers . Try it online!

## Background

Let p0, p1, p2, ⋯ be the sequence of prime numbers in ascending order.

For each list of non-negative integers A := [a1, ⋯, an], we map A to p0z(A)p1a1⋯pnan, where z(A) is the number of trailing zeroes of A.

Reversing the above map in straightforward. For a positive integer k, we factorize it uniquely as the product of consecutive prime powers n = p0α0p1α1⋯pnαn, where αn > 0, then reconstruct the list as 1, ⋯, αn], appending α0 zeroes.

## How it works

### List to integer

TṪạL;³ÆẸ  Main link. Argument: A (list of non-negative integers)

T         Yield all indices of A that correspond to truthy (i.e., non-zero) items.
Ṫ        Tail; select the last truthy index.
This returns 0 if the list is empty.
L      Yield the length of A.
ạ       Compute the absolute difference of the last truthy index and the length.
This yields the amount of trailing zeroes of A.
;³    Prepend the difference to A.
ÆẸ  Convert the list from prime exponents to integer.


### Integer to list

ÆE©Ḣ0ẋ®;  Main link. Input: k (positive integer)

ÆE        Convert k to the list of its prime exponents.
©       Save the list of prime exponents in the register.
Ḣ      Head; pop the first exponent.
If the list is empty, this yields 0.
0ẋ    Construct a list of that many zeroes.
®;  Concatenate the popped list of exponents with the list of zeroes.


## Example output

The first one hundred positive integers map to the following lists.

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

• This is brilliant. May 1 '16 at 6:21

# Jelly, 13 12 bytes

## Encode, 7 6 bytes

2Bṁx‘Ḅ


Try it online!

## Decode, 6 bytes

ȯIBŒɠ’


Try it online!

Encodes positive integers in the run lengths of the binary representation. Since we may have zeros, we increment all numbers. For example, the list [0,1,4] is encoded as 10011111 in binary.

Numbers from 0 to 100 (Try it online!):

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


# Python 2, 88 bytes

d=lambda n:map(len,bin(n).split('1')[1:])
e=lambda l:int('1'.join(a*'0'for a in[2]+l),2)


Demo:

>>> for i in range(33):
...     print e(d(i)), d(i)
...
0 []
1 [0]
2 [1]
3 [0, 0]
4 [2]
5 [1, 0]
6 [0, 1]
7 [0, 0, 0]
8 [3]
9 [2, 0]
10 [1, 1]
11 [1, 0, 0]
12 [0, 2]
13 [0, 1, 0]
14 [0, 0, 1]
15 [0, 0, 0, 0]
16 [4]
17 [3, 0]
18 [2, 1]
19 [2, 0, 0]
20 [1, 2]
21 [1, 1, 0]
22 [1, 0, 1]
23 [1, 0, 0, 0]
24 [0, 3]
25 [0, 2, 0]
26 [0, 1, 1]
27 [0, 1, 0, 0]
28 [0, 0, 2]
29 [0, 0, 1, 0]
30 [0, 0, 0, 1]
31 [0, 0, 0, 0, 0]
32 [5]


# Python 2, 130 bytes

Here’s a more “efficient” solution where the bit-length of the output is linear in the bit-length of the input rather than exponential.

def d(n):m=-(n^-n);return d(n/m/m)+[n/m%m+m-2]if n else[]
e=lambda l:int('0'+''.join(bin(2*a+5<<len(bin(a+2))-4)[3:]for a in l),2)

• Uses the same algorithm as my solution :) May 1 '16 at 10:01
• @KennyLau: I hadn’t looked at your solution. They look similar but not identical (0s and 1s are swapped). And yours fails to round-trip the empty list. May 1 '16 at 10:06
• I see, thanks for reminding. May 1 '16 at 10:11
• By the way, I said the output can be in any base. May 1 '16 at 11:27
• Since sharing code between the functions is allowed, it looks like you can just build e to be the inverse for d: e=lambda l,i=0:l!=d(i)and-~e(l,i+1).
– xnor
May 2 '16 at 5:54

# Python 2, 204 202 bytes

p=lambda x,y:(2*y+1<<x)-1
u=lambda n,x=0:-~n%2<1and u(-~n//2-1,x+1)or[x,n//2]
e=lambda l:l and-~reduce(p,l,len(l)-1)or 0
def d(n):
if n<1:return[]
r=[];n,l=u(n-1);exec"n,e=u(n);r=[e]+r;"*l;return[n]+r


Works by repeatedly applying a Z+ x Z+ <-> Z+ bijection, prepended by the list length.

0: []
1: [0]
2: [1]
3: [0, 0]
4: [2]
5: [0, 0, 0]
6: [1, 0]
7: [0, 0, 0, 0]
8: [3]
9: [0, 0, 0, 0, 0]
10: [1, 0, 0]
11: [0, 0, 0, 0, 0, 0]
12: [0, 1]
13: [0, 0, 0, 0, 0, 0, 0]
14: [1, 0, 0, 0]
15: [0, 0, 0, 0, 0, 0, 0, 0]
16: [4]
17: [0, 0, 0, 0, 0, 0, 0, 0, 0]
18: [1, 0, 0, 0, 0]
19: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
20: [0, 0, 1]
21: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
22: [1, 0, 0, 0, 0, 0]
23: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
24: [2, 0]
25: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
26: [1, 0, 0, 0, 0, 0, 0]
27: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
28: [0, 0, 0, 1]
29: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
30: [1, 0, 0, 0, 0, 0, 0, 0]
31: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

• One question: which function is the "list to integer" function, and which is the "integer to list" function? May 1 '16 at 8:46
• @zyabin101 e is list to integer, d is integer to list (encode/decode).
– orlp
May 1 '16 at 9:06
• I like this solution. May 1 '16 at 11:14

# Retina, 17 + 23 = 40 bytes

From list to integer:

\d+
$&$*0
^
1

1


Try it online!

From integer to list:

^1

S1
m^(0*)
\$.1
¶
<space>


Try it online!

Uses Kaseorg's Algorithm.

# JavaScript, 87 bytes

F=n=>n.toString(2).split(1).slice(1).map(_=>_.length)
G=a=>g=(i=0)=>F(i)+''==a?i:g(++i)


G goes through all inputs since it's shorter