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.
- 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.
<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]
Tcl
Inspired by the D solution. <lang tcl>package require Tcl 8.6
proc rank {integers} {
scan [join [lmap i $integers {format %llo $i}] 8] %lld
}
proc unrank {codedValue} {
lmap i [split $codedValue 8] {scan $i %llo}
}</lang> Demonstrating: <lang tcl>set s {1 2 3 10 100 987654321 135792468107264516704251 7} puts "prior: $s" set c [rank $s] puts "encoded: $c" set t [unrank $c] puts "after: $t"</lang>
- Output:
prior: 1 2 3 10 100 987654321 135792468107264516704251 7 encoded: 1828381281448726746426183460251416730347660304377387 after: 1 2 3 10 100 987654321 135792468107264516704251 7