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.

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 xx $dimension, @reversed-digits[$_, * + $dimension ... *].reverse

   }, ^$dimension;

}

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

   my $dimension = @n.elems;
   reduce * * $dimension + *,
   0 xx $dimension, 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