Index finite lists of positive integers

It is known that the set of finite lists of positive integers is countable. This means that there exists a subset of natural integers which can be mapped to the set of finite lists of positive integers. The purpose of this task is to implement such a mapping :

• write a function rank which assigns an integer to any finite, arbitrarily long list of arbitrary large integers.

Index finite lists of positive integers is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

• write a function unrank which is rank 's inverse function.

Demonstrate your solution by picking a random-length list of random positive integers, turn it into an integer and get the list back.

D

This solution isn't efficient.

Translation of: Python

<lang d>import std.stdio, std.algorithm, std.array, std.conv, std.bigint;

BigInt rank(T)(in T[] x) pure /*nothrow @safe*/ {

   return BigInt("0x" ~ x.map!text.join("F"));

}

BigInt[] unrank(BigInt n) pure /*nothrow @safe*/ {

   string s;
   while (n) {
       s = "0123456789ABCDEF"[n % 16] ~ s;
       n /= 16;
   }
   return s.split("F").map!BigInt.array;

}

void main() {

   immutable s = [1, 2, 3, 10, 100, 987654321];
   s.writeln;
   s.rank.writeln;
   s.rank.unrank.writeln;

}</lang>

Output:

[1, 2, 3, 10, 100, 987654321]
37699814998383067155219233
[1, 2, 3, 10, 100, 987654321]

J

Implementation:

<lang j>scrunch=:3 :0

 n=.1x+>./y
 #.(1#~##:n),0,n,&#:n#.y

)

hcnurcs=:3 :0

 b=.#:y
 m=.b i.0
 n=.#.m{.(m+1)}.b
 n #.inv#.(1+2*m)}.b

)</lang>

Example use:

<lang J> scrunch 4 5 7 9 0 8 8 7 4 8 8 4 1 4314664669630761

  hcnurcs 4314664669630761

4 5 7 9 0 8 8 7 4 8 8 4 1</lang>

Perl 6

<lang perl6>sub expand(Int $n is copy, Int $dimension where * > 1) {

   my @reversed-digits = gather while $n > 0 {

take $n % $dimension; $n div= $dimension;

   }
   return map {

reduce * * $dimension + *, 0, 0, reverse @reversed-digits[$_, * + $dimension ... *]

   }, ^$dimension;

}

sub compress(*@n is copy where @n > 1) {

   my $dimension = @n.elems;
   reduce * * $dimension + *, 0, 0
   reverse gather while @n.any > 0 {

(state $i = 0) %= $dimension; take @n[$i] % $dimension; @n[$i] div= $dimension; $i++;

   }

}

sub rank(@n) { compress compress(@n), +@n } sub unrank(Int $n) { expand |expand($n, 2) }

say my @list = (^10).roll((2..20).pick); say my $rank = rank @list; say unrank $rank;</lang>

Output:

4 5 7 9 0 8 8 7 4 8 8 4 1
406578125236287223374090483
4 5 7 9 0 8 8 7 4 8 8 4 1

Python

<lang python>def rank(x): return int('a'.join(map(str, x)), 11)

def unrank(n): s = while n: s,n = "0123456789a"[n%11] + s, n//11 return map(int, out.split('a'))

l = [1, 2, 3, 10, 100, 987654321] print l n = rank(l) print n l = unrank(n) print l</lang>

Output:

[1, 2, 3, 10, 100, 987654321]
14307647611639042485573
[1, 2, 3, 10, 100, 987654321]