11
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ "However, now the list will consist of non-negative numbers." \$\endgroup\$ – Leaky Nun May 1 '16 at 5:53
  • \$\begingroup\$ So, to be clear, we're mapping N^inf -> N? \$\endgroup\$ – Mego May 1 '16 at 5:56
  • \$\begingroup\$ @Mego N^inf is not countable. N^k where k is any finite number is. \$\endgroup\$ – Leaky Nun May 1 '16 at 5:57
  • \$\begingroup\$ We have been discussing about this in chat. \$\endgroup\$ – Leaky Nun May 1 '16 at 5:57
  • \$\begingroup\$ 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. \$\endgroup\$ – Dennis May 1 '16 at 5:59
10
\$\begingroup\$

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]
\$\endgroup\$
  • \$\begingroup\$ This is brilliant. \$\endgroup\$ – Leaky Nun May 1 '16 at 6:21
3
\$\begingroup\$

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)
\$\endgroup\$
  • \$\begingroup\$ Uses the same algorithm as my solution :) \$\endgroup\$ – Leaky Nun May 1 '16 at 10:01
  • \$\begingroup\$ @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. \$\endgroup\$ – Anders Kaseorg May 1 '16 at 10:06
  • \$\begingroup\$ I see, thanks for reminding. \$\endgroup\$ – Leaky Nun May 1 '16 at 10:11
  • \$\begingroup\$ By the way, I said the output can be in any base. \$\endgroup\$ – Leaky Nun May 1 '16 at 11:27
  • \$\begingroup\$ 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). \$\endgroup\$ – xnor May 2 '16 at 5:54
1
\$\begingroup\$

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]
\$\endgroup\$
  • \$\begingroup\$ One question: which function is the "list to integer" function, and which is the "integer to list" function? \$\endgroup\$ – user48538 May 1 '16 at 8:46
  • \$\begingroup\$ @zyabin101 e is list to integer, d is integer to list (encode/decode). \$\endgroup\$ – orlp May 1 '16 at 9:06
  • \$\begingroup\$ I like this solution. \$\endgroup\$ – Leaky Nun May 1 '16 at 11:14
0
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.