Index finite lists of positive 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.

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.

• 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]