13
\$\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.

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

6 Answers 6

Reset to default
12
\$\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]
Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ This is brilliant. \$\endgroup\$ Commented May 1, 2016 at 6:21
7
\$\begingroup\$

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]
Improve this answer
\$\endgroup\$
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)
Improve this answer
\$\endgroup\$
4
  • \$\begingroup\$ Uses the same algorithm as my solution :) \$\endgroup\$ Commented May 1, 2016 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\$ Commented May 1, 2016 at 10:06
  • \$\begingroup\$ By the way, I said the output can be in any base. \$\endgroup\$ Commented May 1, 2016 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\$ Commented May 2, 2016 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]
Improve this answer
\$\endgroup\$
3
  • \$\begingroup\$ One question: which function is the "list to integer" function, and which is the "integer to list" function? \$\endgroup\$ Commented May 1, 2016 at 8:46
  • \$\begingroup\$ @zyabin101 e is list to integer, d is integer to list (encode/decode). \$\endgroup\$ Commented May 1, 2016 at 9:06
  • \$\begingroup\$ I like this solution. \$\endgroup\$ Commented May 1, 2016 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.

Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ 16 bytes. \$\endgroup\$ Commented Jul 4, 2022 at 6:33
  • \$\begingroup\$ 14 bytes. \$\endgroup\$ Commented Jul 4, 2022 at 6:35
0
\$\begingroup\$

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

Improve this answer
\$\endgroup\$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.