Map a list of indefinite size to a number!

Question

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 code-golf. Lowest score wins.

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

Answer 1

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 p₀, p₁, p₂, ⋯ be the sequence of prime numbers in ascending order.

For each list of non-negative integers A := [a₁, ⋯, a_n], we map A to p₀^z(A)p₁^a₁⋯p_n^a_n, 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 = p₀^α₀p₁^α₁⋯p_n^α_n, where α_n > 0, then reconstruct the list as [α₁, ⋯, α_n], appending α₀ 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]

Answer 2

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]         

Answer 3

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)

Answer 4

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]

Answer 5

Retina, 17 + 23 = 40 bytes

From list to integer:

\d+
$&$*0
^
1
 
1

Try it online!

From integer to list:

^1

S`1
m`^(0*)
$.1
¶
<space>

Try it online!

Uses Kaseorg's Algorithm.

Answer 6

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