Index finite lists of positive integers: Difference between revisions

From Rosetta Code
Content added Content deleted
(→‎{{header|REXX}}: added the REXX language. -- ~~~~)
(Updated D entry)
Line 20: Line 20:
<lang d>import std.stdio, std.algorithm, std.array, std.conv, std.bigint;
<lang d>import std.stdio, std.algorithm, std.array, std.conv, std.bigint;


BigInt rank(T)(in T[] x) pure /*nothrow @safe*/ {
BigInt rank(T)(in T[] x) pure /*nothrow*/ @safe {
return BigInt("0x" ~ x.map!text.join("F"));
return BigInt("0x" ~ x.map!text.join('F'));
}
}


Line 30: Line 30:
n /= 16;
n /= 16;
}
}
return s.split("F").map!BigInt.array;
return s.split('F').map!BigInt.array;
}
}


Revision as of 16:13, 5 January 2015

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.

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.

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]

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 versions

Base 11 encoding:

<lang j> rank =. 11&#.@:}.@:>@:(,&:>/)@:(<@:(10&,)@:(10&#.^:_1)"0)@:x: 

  unrank=. 10&#.;._1@:(10&,)@:(11&#.^:_1)</lang>

Example use:

<lang J> rank 1 2 3 10 100 987654321 135792468107264516704251 7x 187573177082615698496949025806128189691804770100426 

  unrank 187573177082615698496949025806128189691804770100426x

1 2 3 10 100 987654321 135792468107264516704251 7</lang>

Prime factorization (Gödelian) encoding:

<lang j> rank=. */@:(^~ p:@:i.@:#)@:>:@:x: 

  unrank=. <:@:(#;.1@:~:@:q:)</lang>

Example use:

<lang J> rank 1 11 16 1 3 9 0 2 15 7 19 10 6857998574998940803374702726455974765530187550029640884386375715876970128518999225074067307280381624132537960815429687500 

  unrank 6857998574998940803374702726455974765530187550029640884386375715876970128518999225074067307280381624132537960815429687500x

1 11 16 1 3 9 0 2 15 7 19 10</lang>

Bijective

Using the method of the Python version (shifted):

<lang j> rank=. 1 -~ #.@:(1 , >@:(([ , 0 , ])&.>/)@:(<@:($&1)"0))@:x: 

  unrank=. #;._2@:((0 ,~ }.)@:(#.^:_1)@:(1&+))</lang>

Example use:

<lang J> >@:((] ; unrank ; rank@:unrank)&.>)@:i. 11 ┌──┬───────┬──┐ │0 │0 │0 │ ├──┼───────┼──┤ │1 │0 0 │1 │ ├──┼───────┼──┤ │2 │1 │2 │ ├──┼───────┼──┤ │3 │0 0 0 │3 │ ├──┼───────┼──┤ │4 │0 1 │4 │ ├──┼───────┼──┤ │5 │1 0 │5 │ ├──┼───────┼──┤ │6 │2 │6 │ ├──┼───────┼──┤ │7 │0 0 0 0│7 │ ├──┼───────┼──┤ │8 │0 0 1 │8 │ ├──┼───────┼──┤ │9 │0 1 0 │9 │ ├──┼───────┼──┤ │10│0 2 │10│ └──┴───────┴──┘ 

  (] ; rank ; unrank@:rank) 1 2 3 5 8

┌─────────┬────────┬─────────┐ │1 2 3 5 8│14401278│1 2 3 5 8│ └─────────┴────────┴─────────┘</lang>

Perl 6

Here is a cheap solution using a base-11 encoding and string operations: <lang perl6>sub rank(*@n) { :11(@n.join('A')) } sub unrank(Int $n) { $n.base(11).split('A') }

say my @n = (^20).roll(12); say my $n = rank(@n); say unrank $n;</lang>

Output:
1 11 16 1 3 9 0 2 15 7 19 10
25155454474293912130094652799
1 11 16 1 3 9 0 2 15 7 19 10

Here is a bijective solution that does not use string operations.

<lang perl6>multi infix:<rad> () { 0 } multi infix:<rad> ($a) { $a } multi infix:<rad> ($a, $b) { $a * $*RADIX + $b }

multi expand(Int $n is copy, 1) { $n } multi expand(Int $n is copy, Int $*RADIX) { 

   my \RAD = $*RADIX;

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

take $n % RAD; $n div= RAD; 

   }

   eager for ^RAD {

[rad] reverse @reversed-digits[$_, * + RAD ... *] 

   }

}

multi compress(@n where @n == 1) { @n[0] } multi compress(@n is copy) { 

   my \RAD = my $*RADIX = @n.elems;

   [rad] reverse gather while @n.any > 0 {

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

sub rank(@n) { compress (compress(@n), @n - 1)} sub unrank(Int $n) { my ($a, $b) = expand $n, 2; expand $a, $b + 1 }

my @list = (^10).roll((2..20).pick); my $rank = rank @list; say "[$@list] -> $rank -> [{unrank $rank}]";

for ^10 { 

   my @unrank = unrank $_;
   say "$_ -> [$@unrank] -> {rank @unrank}";

}</lang>

Output:
[7 1 4 7 7 0 2 7 7 0 7 7] -> 20570633300796394530947471 -> [7 1 4 7 7 0 2 7 7 0 7 7]
0 -> [0] -> 0
1 -> [1] -> 1
2 -> [0 0] -> 2
3 -> [1 0] -> 3
4 -> [2] -> 4
5 -> [3] -> 5
6 -> [0 1] -> 6
7 -> [1 1] -> 7
8 -> [0 0 0] -> 8
9 -> [1 0 0] -> 9

Python

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

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

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

Output:
[0, 1, 2, 3, 10, 100, 987654321]
207672721333439869642567444
[0, 1, 2, 3, 10, 100, 987654321]

Bijection

Each number in the list is stored as a length of 1s, separated by 0s, and the resulting string is prefixed by '1', then taken as a binary number. Empty list is mapped to 0 as a special case. Don't use it on large numbers. <lang python>def unrank(n): 

       return map(len, bin(n)[3:].split("0")) if n else []

def rank(x): 

       return int('1' + '0'.join('1'*a for a in x), 2) if x else 0

for x in range(11): 

       print x, unrank(x), rank(unrank(x))

print x = [1, 2, 3, 5, 8]; print x, rank(x), unrank(rank(x)) </lang>

Output:
0 [] 0
1 [0] 1
2 [0, 0] 2
3 [1] 3
4 [0, 0, 0] 4
5 [0, 1] 5
6 [1, 0] 6
7 [2] 7
8 [0, 0, 0, 0] 8
9 [0, 0, 1] 9
10 [0, 1, 0] 10

[1, 2, 3, 5, 8] 14401279 [1, 2, 3, 5, 8]

REXX

<lang rexx>/*REXX pgm assigns an int for a finite list of arbitrary positive ints.*/ parse arg L /*get optional list of pos. ints.*/ if L= then L=3 14 159 2653589793238 /*L not specified? Use default.*/ L=translate(space(L),','," ") /*use a commatized list of nums. */ numeric digits max(9,2*length(L)) /*ensure enough digs to handle L.*/ 

             say 'original list=' L   /*display the original list of #s*/

N=rank(L); say ' map integer=' N /*generate & show the map integer*/ O=unrank(N); say ' unrank=' O /*generate original # & show it.*/ exit /*stick a fork in it, we're done.*/ /*──────────────────────────────────one-liner subroutines───────────────*/ rank: return x2d(translate(space(arg(1)),'c',",")) unrank: return space(translate(d2x(arg(1)),',',"C"))</lang> output when using the default input: 

original list= 3,14,159,2653589793238
  map integer= 72633563195984664801653304
       unrank= 3,14,159,2653589793238

Ruby

Translation of: Python

<lang ruby>def rank(arr) 

 arr.join('a').to_i(11)

end

def unrank(n) 

 n.to_s(11).split('a').collect{|x| x.to_i}

end

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

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

Bijection

Translation of: Python

<lang ruby>def unrank(n) 

 return [0] if n==1
 n.to_s(2)[1..-1].split('0',-1).map(&:size)

end

def rank(x) 

 return 0 if x.empty?
 ('1' + x.map{ |a| '1'*a }.join('0')).to_i(2)

end

for x in 0..10 

 puts "%3d : %-18s: %d" % [x, a=unrank(x), rank(a)]

end

puts x = [1, 2, 3, 5, 8] puts "#{x} => #{rank(x)} => #{unrank(rank(x))}"</lang>

Output:
  0 : []                : 0
  1 : [0]               : 1
  2 : [0, 0]            : 2
  3 : [1]               : 3
  4 : [0, 0, 0]         : 4
  5 : [0, 1]            : 5
  6 : [1, 0]            : 6
  7 : [2]               : 7
  8 : [0, 0, 0, 0]      : 8
  9 : [0, 0, 1]         : 9
 10 : [0, 1, 0]         : 10

[1, 2, 3, 5, 8] => 14401279 => [1, 2, 3, 5, 8]

Tcl

Works with: Tcl version 8.6

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

zkl

Using GMP, base 11 and sometimes strings to represent big ints. <lang zkl>var BN=Import("zklBigNum"); fcn rank(ns) { BN(ns.concat("A"),11) } fcn unrank(bn) { bn.toString(11).split("a").apply("toInt") } fcn unrankS(bn){ bn.toString(11).split("a") }</lang> <lang zkl>fcn rankz(ns,S=False){ 

  ns.println();
  rank(ns).println();
  if(S) ns:rank(_):unrankS(_).println();
  else  ns:rank(_):unrank(_) .println();

} rankz(T(1,2,3,10,100,987654321)); rankz(T(1,2,3,10,100,987654321,"135792468107264516704251",7),True);</lang>

Output:
L(1,2,3,10,100,987654321)
14307647611639042485573
L(1,2,3,10,100,987654321)
L(1,2,3,10,100,987654321,"135792468107264516704251",7)
187573177082615698496949025806128189691804770100426
L("1","2","3","10","100","987654321","135792468107264516704251","7")
Retrieved from "https://rosettacode.org/wiki/Index_finite_lists_of_positive_integers?oldid=246830"