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.
There are many ways to do this. Feel free to choose any one you like.
Extra credit:
Make rank as a bijection and show unrank(n) for n varying from 0 to 10.
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]
Go
<lang go>package main
import (
"fmt" "math/big" "math/rand" "strings" "time"
)
// Join base 10 representations with an "a" and you get a base 11 number. // Unfortunately base 11 is a little awkward with big.Int, so just treat it as base 16. func rank(l []big.Int) *big.Int {
s := make([]string, len(l))
for i, n := range l {
s[i] = n.String()
}
i, ok := new(big.Int).SetString(strings.Join(s, "a"), 16)
if !ok {
panic("huh")
}
return i
}
// Split the base 16 representation at "a", recover the base 10 numbers. func unrank(r *big.Int) []big.Int {
s := strings.Split(fmt.Sprintf("%x", r), "a")
l := make([]big.Int, len(s))
for i, s1 := range s {
_, ok := l[i].SetString(s1, 10)
if !ok {
panic("really")
}
}
return l
}
func main() {
l := random()
fmt.Println("List:")
for _, n := range l {
fmt.Println(" ", &n)
}
r := rank(l)
fmt.Println("Rank:")
fmt.Println(" ", r)
u := unrank(r)
fmt.Println("Unranked:")
for _, n := range u {
fmt.Println(" ", &n)
}
}
// returns 3 to 10 numbers in the range 1 to 2^100 func random() []big.Int {
r := rand.New(rand.NewSource(time.Now().Unix()))
l := make([]big.Int, 3+r.Intn(8))
one := big.NewInt(1)
max := new(big.Int).Lsh(one, 100)
for i := range l {
l[i].Add(one, l[i].Rand(r, max))
}
return l
}</lang>
- Output:
List: 250046378143152073779399139308 433677733115839140356036818773 709681404405498840918712626000 Rank: 86898591846547743089837040293705765764160568618712035006919317223922729203294339688481288514295259746298650624 Unranked: 250046378143152073779399139308 433677733115839140356036818773 709681404405498840918712626000
J
Explicit version
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>
Explanation. We treat the sequence as an n digit number in base m where n is the length of the list and m is 1+the largest value in the list. (This is equivalent to treating it as a polynomial in m with coefficients which are the values of the list.) In other words 4 5 7 9 0 8 8 7 4 8 8 4 1 becomes 4579088748841. Now we just need to encode the base (10, in this case). To do that we treat this number as a sequence of bits and prepend it with 1 1 1 1 0 1 0 1 0. This is a sequence of '1's whose length matches the number of bits needed to represent the base of our polynomial, followed by a 0 followed by the base of our polynomial.
To extract the original list we reverse this process: Find the position of the first zero, that's the size of our base, extract the base and then use that to find the coefficients of our polynomial, which is or original list.
Whether this is an efficient representation or not depends, of course, on the nature of the list being represented.
Tacit version
Implementation:
<lang j> rank =. 11&#.@:>@:(,&:>/)@:(<@:(10&,)@:(10&#.^:_1)"0)@:x:
unrank=. 10&#.;._1@:(11&#.^:_1)</lang>
Example use:
<lang J> rank 1 2 3 10 100 987654321 135792468107264516704251 7x 10859468893418553562739357752202339093235635587121336
unrank 10859468893418553562739357752202339093235635587121336x
1 2 3 10 100 987654321 135792468107264516704251 7</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
Extra credit
To get a bijection we need to shift the encoding of the length by two:
<lang perl6>sub rank(@n) { compress compress(@n), +@n - 2} sub unrank(Int $n) { my ($a, $b) = expand($n, 2); expand $a, $b + 2 }
for ^10 {
my @unrank = unrank $_; say @unrank, " <-> ", rank @unrank;
}</lang>
- Output:
0 0 <-> 0 1 0 <-> 1 0 0 0 <-> 2 1 0 0 <-> 3 0 1 <-> 4 1 1 <-> 5 2 0 0 <-> 6 0 1 0 <-> 7 0 0 0 0 <-> 8 1 0 0 0 <-> 9 0 0 0 0 0 <-> 10
This does not deal with the degenerate case of lists of length one, though.
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, s.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} {
join [lmap i $integers {format %llo $i}] 8
}
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