Rosetta Code

Index finite lists of positive integers: Difference between revisions

Page Discussion

Index finite lists of positive integers (view source)

Revision as of 08:39, 1 February 2024

46,613 bytes added ,  3 months ago
→‎{{header|jq}}: simplify
(→‎{{header|Perl 6}}: using base 11 instead)
(→‎{{header|jq}}: simplify)
 
(78 intermediate revisions by 30 users not shown)
Line 1:
{{draft task}}
 
It is known that the set of finite lists of positive integers is &nbsp; [[wp:countable| <u>countable</u>]]. 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 :
 
*This writemeans that there exists a functionsubset ''rank''of natural integers which assignscan anbe integermapped to anythe finite,set arbitrarilyof longfinite listlists of arbitrary largepositive integers.
 
* write a function ''unrank'' which is ''rank'' 's [[wp:inverse function|inverse function]].
 
;Task:
Demonstrate your solution by picking a random-length list of random positive integers, turn it into an integer and get the list back.
Implement such a mapping:
:* &nbsp; write a function &nbsp; &nbsp; ''rank'' &nbsp; &nbsp; which assigns an integer to any finite, arbitrarily long list of arbitrary large positive integers.
:* &nbsp; write a function &nbsp; ''unrank'' &nbsp; which is the &nbsp; ''rank'' &nbsp; [[wp:inverse function| <u>inverse function</u>]].
 
There are many ways to do this. Feel free to choose any one you like.
 
Demonstrate your solution by:
'''Extra credit''':
:* &nbsp; picking a random-length list of random positive integers
:* &nbsp; turn it into an integer, &nbsp; and
:* &nbsp; get the list back.
 
 
Make rank as a [[wp:bijection|bijection]] and show unrank(n) for n varying from 0 to 10.
There are many ways to do this. &nbsp; Feel free to choose any one you like.
 
 
;Extra credit:
Make the &nbsp; ''rank'' &nbsp; function as a &nbsp; [[wp:bijection| <u>bijection</u>]] &nbsp; and show &nbsp; ''unrank(n)'' &nbsp; for &nbsp; <big>'''n'''</big> &nbsp; varying from &nbsp; '''0''' &nbsp; to &nbsp; '''10'''.
<br><br>
 
=={{header|11l}}==
{{trans|Python}}
 
<syntaxhighlight lang="11l">F rank(x)
R BigInt(([1] [+] x).map(String).join(‘A’), radix' 11)
 
F unrank(n)
V s = String(n, radix' 11)
R s.split(‘A’).map(Int)[1..]
 
V l = [1, 2, 3, 10, 100, 987654321]
print(l)
V n = rank(l)
print(n)
l = unrank(n)
print(l)</syntaxhighlight>
 
{{out}}
<pre>
[1, 2, 3, 10, 100, 987654321]
1723765384735274025865314
[1, 2, 3, 10, 100, 987654321]
</pre>
 
=={{header|Arturo}}==
 
<syntaxhighlight lang="rebol">rank: function [arr][
if empty? arr -> return 0
from.binary "1" ++ join.with:"0" map arr 'a -> repeat "1" a
]
 
unrank: function [rnk][
if rnk=1 -> return [0]
bn: as.binary rnk
map split.by:"0" slice bn 1 dec size bn => size
]
 
l: [1, 2, 3, 5, 8]
 
print ["The initial list:" l]
 
r: rank l
print ["Ranked:" r]
 
u: unrank r
print ["Unranked:" u]</syntaxhighlight>
 
{{out}}
 
<pre>The initial list: [1 2 3 5 8]
Ranked: 14401279
Unranked: [1 2 3 5 8]</pre>
 
=={{header|D}}==
This solution isn't efficient.
{{trans|Python}}
<langsyntaxhighlight 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"'));
}
 
Line 30 ⟶ 93:
n /= 16;
}
return s.split("'F"').map!BigInt.array;
}
 
Line 38 ⟶ 101:
s.rank.writeln;
s.rank.unrank.writeln;
}</langsyntaxhighlight>
{{out}}
<pre>[1, 2, 3, 10, 100, 987654321]
Line 44 ⟶ 107:
[1, 2, 3, 10, 100, 987654321]
</pre>
 
=={{header|FreeBASIC}}==
Restricted to shortish lists with smallish integers, because the rank integers get really big really fast, and bloating the code with arbitrary precision arithmetic isn't illustrative.
<syntaxhighlight lang="freebasic">type duple
A as ulongint
B as ulongint
end type
 
function two_to_one( A as ulongint, B as ulongint ) as ulongint 'converts two numbers into one
dim as uinteger ret = A*A + B*B + 2*A*B - 3*A - B 'according to the table
return 1 + ret/2 ' 1 2 3 4 5
end function ' -------------
' 1| 1 3 6 10 15
function one_to_two( R as ulongint ) as duple ' 2| 2 5 9 14 20
dim as uinteger t = int((-1+sqr(8*R-7))/2) ' 3| 4 8 13 19 26
dim as duple ret ' 4| 7 12 18 25 33
ret.A = (t*t+3*t+4)/2-R
t = int((-1+sqr(8*R-7))/2) 'and the inverse of this
ret.B = R-t*(t+1)/2
return ret
end function
 
function rank( N() as ulongint) as ulongint
dim as uinteger ret, num = ubound(N)+1
if num = 0 then return 0 'define a value of 0 for the empty list
if num = 1 then return two_to_one( N(0), 1 )
ret = two_to_one( N(0), N(1) )
for i as uinteger = 2 to num-1 'progressively encode the list by
ret = two_to_one( ret, N(i) ) 'applying 2to1 on the result of the
next i 'previous calculation with the next list element
return two_to_one(ret, num) 'store the length of the list as
end function 'the final component
 
sub unrank( R as ulongint, N() as ulongint )
dim as duple temp
if R = 0 then 'zero yields the empty list
redim N(-1)
return
end if
dim as ulongint num, Q(0 to 1)
temp = one_to_two( R )
num = temp.B 'first get the length of the encoded list
redim N(0 to num-1) as ulongint
if num = 1 then '(singleton handled as a special case)
N(0)=temp.A
return
end if
for i as integer = num-1 to 2 step -1 'get back the list elements one by one
temp = one_to_two( temp.A ) 'in the reverse order they were added
N(i) = temp.B
next i
temp = one_to_two( temp.A ) 'finally get the initial two list elements
N(0) = temp.A
N(1) = temp.B
end sub
 
sub show_list( L() as ulongint )
dim as integer num = ubound(L)
if num=-1 then
print "[]"
return
end if
print "[";
for i as integer = 0 to num-1
print str(L(i))+", ";
next i
print str(L(num))+"]"
end sub
'A few tests
dim as duple temp
redim as uinteger ex0(-1) 'empty list
dim as ulongint R = rank(ex0())
R = rank(ex0())
print R,
redim as ulongint X(0 to 1)
unrank R, X()
show_list(X())
 
dim as uinteger ex1(0 to 0) = {13} 'list with 1 element
R = rank(ex1())
print R,
unrank R, X()
show_list(X())
 
dim as uinteger ex2(0 to 1) = {19, 361} 'list with 2 elements
R = rank(ex2())
print R,
redim as ulongint X(0 to 1)
unrank R, X()
show_list(X())
 
dim as uinteger ex6(0 to 5) = {1,2,1,2,3,1} 'list with 6 elements
R = rank(ex6())
print R,
unrank R, X()
show_list(X())</syntaxhighlight>
{{out}}
<pre>0 []
79 [13]
2591460030 [19, 361]
9576882 [1, 2, 1, 2, 3, 1]</pre>
 
=={{header|Go}}==
'''Bijective'''
<lang go>package main
 
A list element n is encoded as a 1 followed by n 0's. Element encodings are concatenated to form a single integer rank. An advantage of this encoding is that no special case is required to handle the empty list.
<syntaxhighlight lang="go">package main
 
import (
"fmt"
"math/big"
)
 
func rank(l []uint) (r big.Int) {
for _, n := range l {
r.Lsh(&r, n+1)
r.SetBit(&r, int(n), 1)
}
return
}
 
func unrank(n big.Int) (l []uint) {
m := new(big.Int).Set(&n)
for a := m.BitLen(); a > 0; {
m.SetBit(m, a-1, 0)
b := m.BitLen()
l = append(l, uint(a-b-1))
a = b
}
return
}
 
func main() {
var b big.Int
for i := 0; i <= 10; i++ {
b.SetInt64(int64(i))
u := unrank(b)
r := rank(u)
fmt.Println(i, u, &r)
}
b.SetString("12345678901234567890", 10)
u := unrank(b)
r := rank(u)
fmt.Printf("\n%v\n%d\n%d\n", &b, u, &r)
}</syntaxhighlight>
{{out}}
<pre>
0 [] 0
1 [0] 1
2 [1] 2
3 [0 0] 3
4 [2] 4
5 [1 0] 5
6 [0 1] 6
7 [0 0 0] 7
8 [3] 8
9 [2 0] 9
10 [1 1] 10
 
12345678901234567890
[1 1 1 0 1 1 1 2 1 1 2 0 3 0 2 0 0 1 1 0 3 0 0 0 0 4 1 1 0 1 2 1]
12345678901234567890
</pre>
'''Alternative'''
 
A bit of a hack to make a base 11 number then interpret it as base 16, just because that's easiest. Not bijective. Practical though for small lists of large numbers.
<syntaxhighlight lang="go">package main
 
import (
Line 56 ⟶ 283:
)
 
// JoinPrepend base 10 representationsrepresentation 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.
// as base 16.
func rank(l []big.Int) *big.Int {
func rank(l []big.Int) (r big.Int, err error) {
if len(l) == 0 {
return
}
s := make([]string, len(l))
for i, n := range l {
s[i]ns := n.String()
if ns[0] == '-' {
}
return r, fmt.Errorf("negative integers not mapped")
i, ok := new(big.Int).SetString(strings.Join(s, "a"), 16)
if !ok { }
panic(s[i] = "huha") + ns
}
r.SetString(strings.Join(s, ""), 16)
return i
return
}
 
// Split the base 16 representation at "a", recover the base 10 numbers.
func unrank(r *big.Int) ([]big.Int, error) {
ss16 := strings.Split(fmt.Sprintf("%x", &r), "a")
switch {
case s16 == "0":
return nil, nil // empty list
case s16[0] != 'a':
return nil, fmt.Errorf("unrank not bijective")
}
s := strings.Split(s16[1:], "a")
l := make([]big.Int, len(s))
for i, s1 := range s {
if _, ok := l[i].SetString(s1, 10); !ok {
return nil, fmt.Errorf("unrank not bijective")
if !ok {
panic("really")
}
}
return l, nil
}
 
func main() {
l// :=show random()empty list
var l []big.Int
fmt.Println("List:")
r, _ := rank(l)
u, _ := unrank(r)
fmt.Println("Empty list:", l, &r, u)
 
// show random list
l = random()
r, _ = rank(l)
u, _ = unrank(r)
fmt.Println("\nList:")
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)
}
 
// show error with list containing negative
var n big.Int
n.SetInt64(-5)
_, err := rank([]big.Int{n})
fmt.Println("\nList element:", &n, err)
 
// show technique is not bijective
n.SetInt64(1)
_, err = unrank(n)
fmt.Println("Rank:", &n, err)
}
 
// returns 30 to 105 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(86))
one := big.NewInt(1)
max := new(big.Int).Lsh(one, 100)
Line 109 ⟶ 365:
}
return l
}</langsyntaxhighlight>
{{out}}
<pre>
Empty list: [] 0 []
 
List:
170245492534662309353778826165
250046378143152073779399139308
82227712638678862510272817700
433677733115839140356036818773
709681404405498840918712626000
Rank:
17827272030291729487097780664374477811820701746650470453292650775464474368
86898591846547743089837040293705765764160568618712035006919317223922729203294339688481288514295259746298650624
Unranked:
170245492534662309353778826165
250046378143152073779399139308
82227712638678862510272817700
433677733115839140356036818773
 
709681404405498840918712626000
List element: -5 negative integers not handled
Rank: 1 unrank not bijective
</pre>
 
=={{header|Haskell}}==
 
<syntaxhighlight lang="haskell">import Data.List
 
toBase :: Int -> Integer -> [Int]
toBase b = unfoldr f
where
f 0 = Nothing
f n = let (q, r) = n `divMod` fromIntegral b in Just (fromIntegral r, q)
 
fromBase :: Int -> [Int] -> Integer
fromBase n lst = foldr (\x r -> fromIntegral n*r + fromIntegral x) 0 lst
 
------------------------------------------------------------
listToInt :: Int -> [Int] -> Integer
listToInt b lst = fromBase (b+1) $ concat seq
where
seq = [ let (q, r) = divMod n b
in replicate q 0 ++ [r+1]
| n <- lst ]
 
intToList :: Int -> Integer -> [Int]
intToList b lst = go 0 $ toBase (b+1) lst
where
go 0 [] = []
go i (0:xs) = go (i+1) xs
go i (x:xs) = (i*b + x - 1) : go 0 xs</syntaxhighlight>
 
Using different bases we may enumerate lists.
 
<pre>*Main> intToList 2 <$> [1..20]
[[0],[1],[2],[0,0],[1,0],[3],[0,1],[1,1],[4],[0,2],[1,2],[2,0],[0,0,0],[1,0,0],[3,0],[0,1,0],[1,1,0],[5],[0,3],[1,3]]
 
*Main> intToList 3 <$> [1..20]
[[0],[1],[2],[3],[0,0],[1,0],[2,0],[4],[0,1],[1,1],[2,1],[5],[0,2],[1,2],[2,2],[6],[0,3],[1,3],[2,3],[3,0]]
 
*Main> intToList 10 <$> [1..20]
[[0],[1],[2],[3],[4],[5],[6],[7],[8],[9],[10],[0,0],[1,0],[2,0],[3,0],[4,0],[5,0],[6,0],[7,0],[8,0]]
 
*Main> listToInt 2 <$> permutations [1,2,3,4]
[2360,2370,2382,2406,2292,2288,5274,5190,5136,5922,5916,5160,4680,4646,4628,4950,4944,4638,2736,2702,2450,2844,2760,2454]</pre>
 
This mapping is a bijection:
 
<pre>*Main> (listToInt 3 . intToList 3 <$> [0..100]) == [0..100]
True</pre>
 
 
 
 
=={{header|J}}==
 
'''=== Explicit version''' ===
 
Implementation:
 
<langsyntaxhighlight lang="j">scrunch=:3 :0
n=.1x+>./y
#.(1#~##:n),0,n,&#:n#.y
Line 140 ⟶ 450:
n=.#.m{.(m+1)}.b
n #.inv#.(1+2*m)}.b
)</langsyntaxhighlight>
 
Example use:
 
<langsyntaxhighlight Jlang="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</langsyntaxhighlight>
 
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, with powers of m increasing from right to left.) 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.
Line 155 ⟶ 465:
Whether this is an efficient representation or not depends, of course, on the nature of the list being represented.
 
=== Tacit versions ===
 
Base 11 encoding:
'''Tacit version'''
 
<syntaxhighlight lang="j"> rank =. 11&#.@:}.@:>@:(,&:>/)@:(<@:(10&,)@:(10&#.^:_1)"0)@:x:
Implementation:
unrank=. 10&#.;._1@:(10&,)@:(11&#.^:_1)</syntaxhighlight>
 
Example use:
<lang j> rank =. 11&#.@:>@:(,&:>/)@:(<@:(10&,)@:(10&#.^:_1)"0)@:x:
 
unrank=. 10&#.;._1@:(11&#.^:_1)</lang>
<syntaxhighlight lang="j"> rank 1 2 3 10 100 987654321 135792468107264516704251 7x
187573177082615698496949025806128189691804770100426
unrank 187573177082615698496949025806128189691804770100426x
1 2 3 10 100 987654321 135792468107264516704251 7</syntaxhighlight>
 
Prime factorization (Gödelian) encoding:
 
<syntaxhighlight lang="j"> rank=. */@:(^~ p:@:i.@:#)@:>:@:x:
unrank=. <:@:(#;.1@:~:@:q:)</syntaxhighlight>
 
Example use:
 
<langsyntaxhighlight Jlang="j"> rank 1 211 16 1 3 109 1000 9876543212 13579246810726451670425115 7x7 19 10
6857998574998940803374702726455974765530187550029640884386375715876970128518999225074067307280381624132537960815429687500
10859468893418553562739357752202339093235635587121336
unrank 6857998574998940803374702726455974765530187550029640884386375715876970128518999225074067307280381624132537960815429687500x
unrank 10859468893418553562739357752202339093235635587121336x
1 11 16 1 3 9 0 2 15 7 19 10</syntaxhighlight>
1 2 3 10 100 987654321 135792468107264516704251 7</lang>
 
=== Bijective ===
=={{header|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') }
 
Using the method of the Python version (shifted):
say my @n = (^20).roll(12);
say my $n = rank(@n);
say unrank $n;</lang>
{{out}}
<pre>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</pre>
 
<syntaxhighlight lang="j"> rank=. 1 -~ #.@:(1 , >@:(([ , 0 , ])&.>/)@:(<@:($&1)"0))@:x:
Here is a bijective solution that does not use string operations.
unrank=. #;._2@:((0 ,~ }.)@:(#.^:_1)@:(1&+))</syntaxhighlight>
 
Example use:
<lang perl6>sub expand(Int $n is copy, Int $dimension where * > 0) {
 
return $n if $dimension == 1;
<syntaxhighlight lang="j"> >@:((] ; unrank ; rank@:unrank)&.>)@:i. 11
my @reversed-digits = gather while $n > 0 {
┌──┬───────┬──┐
take $n % $dimension;
│0 │0 │0 │
$n div= $dimension;
├──┼───────┼──┤
│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│
└─────────┴────────┴─────────┘</syntaxhighlight>
 
=={{header|Java}}==
Translation of [[Index_finite_lists_of_positive_integers#Python|Python]] via [[Index_finite_lists_of_positive_integers#D|D]]
{{works with|Java|8}}
<syntaxhighlight lang="java">import java.math.BigInteger;
import static java.util.Arrays.stream;
import java.util.*;
import static java.util.stream.Collectors.*;
 
public class Test3 {
static BigInteger rank(int[] x) {
String s = stream(x).mapToObj(String::valueOf).collect(joining("F"));
return new BigInteger(s, 16);
}
 
return map {
static List<BigInteger> unrank(BigInteger n) {
reduce * * $dimension + *, 0, 0,
BigInteger sixteen = BigInteger.valueOf(16);
reverse @reversed-digits[$_, * + $dimension ... *]
}, ^$dimension String s = "";
while (!n.equals(BigInteger.ZERO)) {
}
s = "0123456789ABCDEF".charAt(n.mod(sixteen).intValue()) + s;
n = n.divide(sixteen);
sub compress(*@n is copy where @n > 0) {
my $dimension = @n.elems; }
return stream(s.split("F")).map(x -> new BigInteger(x)).collect(toList());
return @n[0] if $dimension == 1;
reduce * * $dimension + *, 0, 0,
reverse gather while @n.any > 0 {
(state $i = 0) %= $dimension;
take @n[$i] % $dimension;
@n[$i] div= $dimension;
$i++;
}
 
public static void main(String[] args) {
int[] s = {1, 2, 3, 10, 100, 987654321};
System.out.println(Arrays.toString(s));
System.out.println(rank(s));
System.out.println(unrank(rank(s)));
}
}</syntaxhighlight>
<pre>[1, 2, 3, 10, 100, 987654321]
37699814998383067155219233
[1, 2, 3, 10, 100, 987654321]</pre>
 
=={{header|jq}}==
'''Works with gojq'''
 
'''Works with jq''' within the limits of jq's support for large integer arithmetic
 
'''Works with jaq within the limits of jaq's support for large integers'''
 
The main point of interest of this entry is probably the use of the
Fibonacci encoding of positive integers (see
e.g. https://en.wikipedia.org/wiki/Fibonacci_coding and
[[:Category:jq/fibonacci.jq]]). This is the focus of the first
subsection. The second subsection focuses on the "n 0s" encoding.
 
The Go implementation of jq supports indefinitely large integers and
so, apart from machine limitations, the programs shown here should
work using gojq without further qualification.
 
The C implementation of jq, as of version 1.6, supports arbitrarily
large literal integers, and the `tonumber` filter retains precision
allowing seamless translation between strings and numbers.
 
The following is slightly more verbose than it need be but for the
sake of compatibility with jaq. Also note that trivial changes would
be required if using jaq as jaq does not (as of this writing in 2024)
support the `include` or `module` directives.
 
===Map based on Fibonacci encoding===
 
Since each Fibonacci-encoded integer ends with "11" and
contains no other instances of "11" before the end,
the original sequence of integers can trivially be recovered after
simple concatenation of the encodings. However, the Fibonacci
encoding of an integer can begin with 0s, so here we simply prefix
the binary string with a "1".
 
For example: 1 2 3 => 11 011 0011 => 1110110011
 
In the following, we will simply interpret
this as an integer in base 2 to avoid unnecessary complications
arising from implementation-specific limits.
<syntaxhighlight lang="jq">
include "fibonacci" {search: "./"}; # see https://rosettacode.org/wiki/Category:Jq/fibonacci.jq
 
# Input: an array of integers
# Output: an integer-valued binary string, being the reverse of the concatenated Fibonacci-encoded values
def rank:
map(fibencode | map(tostring) | join(""))
| "1" + join("");
 
# Input a bitstring or 0-1 integer interpreted as a bitstring
# Output: an array of integers
def unrank:
tostring
| .[1:]
| split("11")
| .[:-1]
| map(. + "11" | fibdecode) ;
 
# Output: a PRN in range(0;$n) where $n is .
def prn:
if . == 1 then 0
else . as $n
| (($n-1)|tostring|length) as $w
| [limit($w; inputs) | tostring] | join("") | sub("^0+";"") | tonumber
| if . < $n then . else $n | prn end
end;
 
### The task
# Encode and decode a random number of distinct positive numbers chosen at random.
# Produce a JSON object showing the set of numbers, their encoding, and
# the result of comparing the original set with the reconstructed set.
def task:
(11 | prn) + 1
| . as $numbers
| [range(0;$numbers) | 100000 | prn + 1]
| . as $numbers
| rank
| . as $encoded
# now decode:
| unrank
| {$numbers, encoded: ($encoded|tonumber), check: ($numbers == .)}
;
 
task
</syntaxhighlight>
'''Invocation''':
<pre>
< /dev/random tr -cd '0-9' | fold -w 1 | jq -nrf index-finite-lists-of-positive-integers.jq
</pre>
{{output}}
<pre>
{
"numbers": [
92408,
42641,
35563,
17028,
49093
],
"encoded": 101000101000001010101000111000001010001000100101100010101010000000010011001001001001000101011000101010100000010000011,
"check": true
}
</pre>
sub rank(@n) { compress compress(@n), +@n - 1}
sub unrank(Int $n) { my ($a, $b) = expand($n, 2); expand $a, $b + 1 }
 
say my @list = (^10).roll((2..20).pick);
say my $rank = rank @list;
say unrank $rank;
 
===Bijective map based on "n 0s" encoding===
for ^10 {
<syntaxhighlight lang="jq">
my @unrank = unrank $_;
### Infrastructure
say $_, " <-> [", @unrank, "] <-> ", rank @unrank;
 
}</lang>
# Input: a string in base $b (2 to 35 inclusive)
# Output: the decimal value
def frombase($b):
def decimalValue:
if 48 <= . and . <= 57 then . - 48
elif 65 <= . and . <= 90 then . - 55 # (10+.-65)
elif 97 <= . and . <= 122 then . - 87 # (10+.-97)
else "decimalValue" | error
end;
reduce (explode|reverse[]|decimalValue) as $x ({p:1};
.value += (.p * $x)
| .p *= $b)
| .value ;
 
def binary_digits:
if . == 0 then 0
else [recurse( if . == 0 then empty else ./2 | floor end ) % 2 | tostring]
| reverse
| .[1:] # remove the leading 0
| join("")
end ;
 
 
### rank and unrank
# Each integer n in the list is mapped to '1' plus n '0's.
# The empty list is mapped to '0'
def rank:
if length == 0 then 0
else reduce .[] as $i ("";
. += "1" + ("0" * $i))
| frombase(2)
end ;
 
def unrank:
if . == 0 then []
else binary_digits
| split("1")
| .[1:]
| map(length)
end ;
 
### Illustration
range(1;11)
| . as $i
| unrank
| . as $unrank
| [$i, $unrank, rank]
</syntaxhighlight>
{{output}}
<pre>
[1,[0],1]
[2,[1],2]
[3,[0,0],3]
[4,[2],4]
[5,[1,0],5]
[6,[0,1],6]
[7,[0,0,0],7]
[8,[3],8]
[9,[2,0],9]
[10,[1,1],10]
</pre>
 
=={{header|Julia}}==
{{trans|Python}}
 
<syntaxhighlight lang="julia">using LinearAlgebra
LinearAlgebra.rank(x::Vector{<:Integer}) = parse(BigInt, "1a" * join(x, 'a'), base=11)
function unrank(n::Integer)
s = ""
while !iszero(n)
ind = n % 11 + 1
n ÷= 11
s = "0123456789a"[ind:ind] * s
end
return parse.(Int, split(s, 'a'))[2:end]
end
 
v = [0, 1, 2, 3, 10, 100, 987654321]
n = rank(v)
v = unrank(n)
println("# v = $v\n -> n = $n\n -> v = $v")</syntaxhighlight>
 
{{out}}
<pre># v = [0, 1, 2, 23, 610, 5100, 7987654321]
-> n = 207672721333439869642567444
77692871663419443
-> v = [0, 1, 2, 3, 10, 100, 987654321]</pre>
1 2 2 6 5 7
 
0 <-> [0] <-> 0
=={{header|Kotlin}}==
1 <-> [1] <-> 1
<syntaxhighlight lang="scala">// version 1.1.2
2 <-> [0 0] <-> 2
 
3 <-> [1 0] <-> 3
import java.math.BigInteger
4 <-> [2] <-> 4
 
5 <-> [3] <-> 5
/* Separates each integer in the list with an 'a' then encodes in base 11. Empty list mapped to '-1' */
6 <-> [0 1] <-> 6
fun rank(li: List<Int>) = when (li.size) {
7 <-> [1 1] <-> 7
8 <-> [0 0 0] < -> 8-BigInteger.ONE
else -> BigInteger(li.joinToString("a"), 11)
9 <-> [1 0 0] <-> 9</pre>
}
 
fun unrank(r: BigInteger) = when (r) {
-BigInteger.ONE -> emptyList<Int>()
else -> r.toString(11).split('a').map { if (it != "") it.toInt() else 0 }
}
 
 
/* Each integer n in the list mapped to '1' plus n '0's. Empty list mapped to '0' */
fun rank2(li:List<Int>): BigInteger {
if (li.isEmpty()) return BigInteger.ZERO
val sb = StringBuilder()
for (i in li) sb.append("1" + "0".repeat(i))
return BigInteger(sb.toString(), 2)
}
 
fun unrank2(r: BigInteger) = when (r) {
BigInteger.ZERO -> emptyList<Int>()
else -> r.toString(2).drop(1).split('1').map { it.length }
}
 
fun main(args: Array<String>) {
var li: List<Int>
var r: BigInteger
li = listOf(0, 1, 2, 3, 10, 100, 987654321)
println("Before ranking : $li")
r = rank(li)
println("Rank = $r")
li = unrank(r)
println("After unranking : $li")
 
println("\nAlternative approach (not suitable for large numbers)...\n")
li = li.dropLast(1)
println("Before ranking : $li")
r = rank2(li)
println("Rank = $r")
li = unrank2(r)
println("After unranking : $li")
 
println()
for (i in 0..10) {
val bi = BigInteger.valueOf(i.toLong())
li = unrank2(bi)
println("${"%2d".format(i)} -> ${li.toString().padEnd(9)} -> ${rank2(li)}")
}
}</syntaxhighlight>
 
{{out}}
<pre>
Before ranking : [0, 1, 2, 3, 10, 100, 987654321]
Rank = 828335141480036653618783
After unranking : [0, 1, 2, 3, 10, 100, 987654321]
 
Alternative approach (not suitable for large numbers)...
 
Before ranking : [0, 1, 2, 3, 10, 100]
Rank = 4364126777249122850009283661412696064
After unranking : [0, 1, 2, 3, 10, 100]
 
0 -> [] -> 0
1 -> [0] -> 1
2 -> [1] -> 2
3 -> [0, 0] -> 3
4 -> [2] -> 4
5 -> [1, 0] -> 5
6 -> [0, 1] -> 6
7 -> [0, 0, 0] -> 7
8 -> [3] -> 8
9 -> [2, 0] -> 9
10 -> [1, 1] -> 10
</pre>
 
=={{header|Mathematica}} / {{header|Wolfram Language}}==
<syntaxhighlight lang="mathematica">ClearAll[Rank,Unrank]
Rank[x_List]:=FromDigits[Catenate[Riffle[IntegerDigits/@x,{{15}},{1,-1,2}]],16]
Unrank[n_Integer]:=FromDigits/@SequenceSplit[IntegerDigits[n,16],{15}]
Rank[{0,1,2,3,10,100,987654321,0}]
Unrank[%]
First@*Unrank@*Rank@*List /@ Range[0, 20]</syntaxhighlight>
{{out}}
<pre>4886947482322057719812858634706703
{0, 1, 2, 3, 10, 100, 987654321, 0}
{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20}</pre>
 
=={{header|Nim}}==
{{trans|Go}}
{{libheader|bignum}}
<syntaxhighlight lang="nim">import strformat, strutils
import bignum
 
func rank(list: openArray[uint]): Int =
result = newInt(0)
for n in list:
result = result shl (n + 1)
result = result.setBit(n)
 
func unrank(n: Int): seq[uint] =
var m = n.clone
var a = if m.isZero: 0u else: m.bitLen.uint
while a > 0:
m = m.clearBit(a - 1)
let b = if m.isZero: 0u else: m.bitLen.uint
result.add(a - b - 1)
a = b
 
when isMainModule:
 
var b: Int
for i in 0..10:
b = newInt(i)
let u = b.unrank()
let r = u.rank()
echo &"{i:2d} {u:>9s} {r:>2s}"
 
b = newInt("12345678901234567890")
let u = b.unrank()
let r = u.rank()
echo &"\n{b}\n{u}\n{r}"</syntaxhighlight>
 
{{out}}
<pre> 0 @[] 0
1 @[0] 1
2 @[1] 2
3 @[0, 0] 3
4 @[2] 4
5 @[1, 0] 5
6 @[0, 1] 6
7 @[0, 0, 0] 7
8 @[3] 8
9 @[2, 0] 9
10 @[1, 1] 10
 
12345678901234567890
@[1, 1, 1, 0, 1, 1, 1, 2, 1, 1, 2, 0, 3, 0, 2, 0, 0, 1, 1, 0, 3, 0, 0, 0, 0, 4, 1, 1, 0, 1, 2, 1]
12345678901234567890</pre>
 
=={{header|Perl}}==
The base-11 approach requires <code>bigint</code> pragma for all but trivial lists. Using <code>ntheory</code> module for base conversions.
{{trans|Raku}}
{{libheader|ntheory}}
<syntaxhighlight lang="perl">use bigint;
use ntheory qw(fromdigits todigitstring);
use feature 'say';
 
sub rank { join '', fromdigits(join('a',@_), 11) }
sub unrank { split 'a', todigitstring(@_[0], 11) }
 
say join ' ', @n = qw<12 11 0 7 9 15 15 5 7 13 5 5>;
say $n = rank(@n);
say join ' ', unrank $n;</syntaxhighlight>
{{out}}
<pre>12 11 0 7 9 15 15 5 7 13 5 5
16588666500024842935939135419
12 11 0 7 9 15 15 5 7 13 5 5</pre>
 
=={{header|Phix}}==
===base 11===
{{trans|Sidef}}
{{libheader|Phix/mpfr}}
Note this is ''not'' supported under pwa/p2js because mpz_set_str() currently only handles bases 2, 8, 10, and 16.
<!--<syntaxhighlight lang="phix">-->
<span style="color: #008080;">without</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">include</span> <span style="color: #004080;">mpfr</span><span style="color: #0000FF;">.</span><span style="color: #000000;">e</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">rank</span><span style="color: #0000FF;">(</span><span style="color: #004080;">mpz</span> <span style="color: #000000;">r</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">sequence</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sprintf</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"%d"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">])</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #7060A8;">mpz_set_str</span><span style="color: #0000FF;">(</span><span style="color: #000000;">r</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">join</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">,</span><span style="color: #008000;">'a'</span><span style="color: #0000FF;">),</span><span style="color: #000000;">11</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">unrank</span><span style="color: #0000FF;">(</span><span style="color: #004080;">mpz</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">split</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">mpz_get_str</span><span style="color: #0000FF;">(</span><span style="color: #000000;">i</span><span style="color: #0000FF;">,</span><span style="color: #000000;">11</span><span style="color: #0000FF;">),</span><span style="color: #008000;">'a'</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #0000FF;">{{</span><span style="color: #000000;">res</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]}}</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">scanf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">],</span><span style="color: #008000;">"%d"</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">res</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">l</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">3</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">10</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">100</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">987654321</span><span style="color: #0000FF;">}</span>
<span style="color: #004080;">mpz</span> <span style="color: #000000;">n</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">()</span>
<span style="color: #000000;">rank</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #000000;">l</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">u</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">unrank</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%V\n"</span><span style="color: #0000FF;">,{{</span><span style="color: #000000;">l</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">mpz_get_str</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">),</span><span style="color: #000000;">u</span><span style="color: #0000FF;">}})</span>
<!--</syntaxhighlight>-->
{{out}}
<pre>
{{1,2,3,10,100,987654321},"14307647611639042485573",{1,2,3,10,100,987654321}}
</pre>
 
===bijective===
{{trans|Python}}
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">unrank</span><span style="color: #0000FF;">(</span><span style="color: #004080;">atom</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sprintf</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"%0b"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">res</span><span style="color: #0000FF;">=</span><span style="color: #008000;">"1"</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">}</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">split</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">[</span><span style="color: #000000;">2</span><span style="color: #0000FF;">..$],</span><span style="color: #008000;">'0'</span><span style="color: #0000FF;">,</span><span style="color: #004600;">false</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span> <span style="color: #000000;">res</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">])</span> <span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">res</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">rank</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">={}</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #000000;">0</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">y</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">x</span><span style="color: #0000FF;">))</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">x</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">y</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #008000;">'1'</span><span style="color: #0000FF;">,</span><span style="color: #000000;">x</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">])</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #004080;">atom</span> <span style="color: #0000FF;">{{</span><span style="color: #000000;">res</span><span style="color: #0000FF;">}}</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">scanf</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"0b1"</span><span style="color: #0000FF;">&</span><span style="color: #7060A8;">join</span><span style="color: #0000FF;">(</span><span style="color: #000000;">y</span><span style="color: #0000FF;">,</span><span style="color: #008000;">'0'</span><span style="color: #0000FF;">),</span><span style="color: #008000;">"%d"</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">res</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">to</span> <span style="color: #000000;">10</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">a</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">unrank</span><span style="color: #0000FF;">(</span><span style="color: #000000;">i</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%3d : %-18v: %d\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">i</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">a</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">rank</span><span style="color: #0000FF;">(</span><span style="color: #000000;">a</span><span style="color: #0000FF;">)})</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">x</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">3</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">5</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">8</span><span style="color: #0000FF;">}</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%v =&gt; %d =&gt; %v\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">x</span><span style="color: #0000FF;">,</span><span style="color: #000000;">rank</span><span style="color: #0000FF;">(</span><span style="color: #000000;">x</span><span style="color: #0000FF;">),</span><span style="color: #000000;">unrank</span><span style="color: #0000FF;">(</span><span style="color: #000000;">rank</span><span style="color: #0000FF;">(</span><span style="color: #000000;">x</span><span style="color: #0000FF;">))})</span>
<!--</syntaxhighlight>-->
{{out}}
<pre>
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}
</pre>
 
=={{header|Python}}==
<langsyntaxhighlight 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]
Line 250 ⟶ 1,022:
print n
l = unrank(n)
print l</langsyntaxhighlight>
{{out}}
<pre>
[0, 1, 2, 3, 10, 100, 987654321]
207672721333439869642567444
14307647611639042485573
[0, 1, 2, 3, 10, 100, 987654321]
</pre>
 
=== Bijection ===
Each number in the list is stored as a length of 1s, separated by 0s, and the resulting string is prefixed by '1', andthen subtractedtaken byas 1a (tobinary makenumber. 0Empty alist validis index),mapped thento taken0 as a binaryspecial numbercase. Don't use it on large numbers.
<langsyntaxhighlight lang="python">def unrank(n):
return map(len, bin(n + 1)[3:].split("0")) if n else []
 
def rank(x):
return int('1' + '0'.join('1'*a for a in x), 2) -if 1x else 0
 
for x in range(11):
print x, unrank(x), rank(unrank(x))
 
print #extra test
x = [1, 2, 3, 5, 8];
print x, rank(x), unrank(rank(x))</lang>
</syntaxhighlight>
{{out}}
<pre>
0 [0] 0
1 [0, 0] 1
2 [10, 0] 2
3 [0, 0, 01] 3
4 [0, 10, 0] 4
5 [10, 01] 5
6 [21, 0] 6
7 [0, 0, 0, 02] 7
8 [0, 0, 10, 0] 8
9 [0, 10, 01] 9
10 [0, 21, 0] 10
 
[1, 2, 3, 5, 8] 1440127814401279 [1, 2, 3, 5, 8]
</pre>
 
=={{header|Quackery}}==
 
<syntaxhighlight lang="quackery"> [ $ "" swap
witheach
[ number$
char A join join ]
11 base put
$->n drop
base release ] is rank ( [ --> n )
 
[ 11 base put
number$
base release
[] $ "" rot
witheach
[ dup char A = iff
[ drop
$->n drop join
$ "" ]
else join ]
drop ] is unrank ( n --> [ )
</syntaxhighlight>
 
{{out}}
Testing in the Quackery shell.
<pre>/O> []
... 5 random 5 + times
... [ 10 random 1+ join ]
... say " Random list: "
... dup echo cr
... rank
... say " That list, ranked: "
... dup echo cr
... unrank
... say "That number, unranked: "
... echo cr
...
Random list: [ 9 9 10 6 1 7 5 2 ]
That list, ranked: 459086440222376570
That number, unranked: [ 9 9 10 6 1 7 5 2 ]
 
Stack empty.</pre>
 
=={{header|Racket}}==
 
{{trans|Tcl}} (which gives credit to [[#D]])
 
<syntaxhighlight lang="racket">#lang racket/base
(require (only-in racket/string string-join string-split))
 
(define (integer->octal-string i)
(number->string i 8))
 
(define (octal-string->integer s)
(string->number s 8))
 
(define (rank is)
(string->number (string-join (map integer->octal-string is) "8")))
 
(define (unrank ranking)
(map octal-string->integer (string-split (number->string ranking 10) "8")))
 
(module+ test
(define loi '(1 2 3 10 100 987654321 135792468107264516704251 7))
(define rnk (rank loi))
(define urk (unrank rnk))
(displayln loi)
(displayln rnk)
(displayln urk))</syntaxhighlight>
 
{{out}}
 
<pre>(1 2 3 10 100 987654321 135792468107264516704251 7)
1828381281448726746426183460251416730347660304377387
(1 2 3 10 100 987654321 135792468107264516704251 7)</pre>
 
=={{header|Raku}}==
(formerly Perl 6)
Here is a cheap solution using a base-11 encoding and string operations:
<syntaxhighlight lang="raku" line>sub rank(*@n) { :11(@n.join('A')) }
sub unrank(Int $n) { $n.base(11).split('A') }
 
say my @n = (1..20).roll(12);
say my $n = rank(@n);
say unrank $n;</syntaxhighlight>
{{out}}
<pre>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</pre>
 
Here is a bijective solution that does not use string operations.
 
<syntaxhighlight lang="raku" line>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}";
}</syntaxhighlight>
 
{{out}}
<pre>[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</pre>
 
=={{header|REXX}}==
This REXX version can handle zeros as well as any sized (decimal) positive integers.
 
No checks are made that the numbers are non-negative integers or malformed integers.
<syntaxhighlight lang="rexx">/*REXX program assigns an integer for a finite list of arbitrary non-negative integers. */
parse arg $ /*obtain optional argument (int list).*/
if $='' | $="," then $=3 14 159 265358979323846 /*Not specified? Then use the default.*/
/* [↑] kinda use decimal digits of pi.*/
$= translate( space($), ',', " ") /*use a commatized list of integers. */
numeric digits max(9, 2 * length($) ) /*ensure enough dec. digits to handle $*/
 
say 'original list=' $ /*display the original list of integers*/
N= rank($); say ' map integer=' N /*generate and display the map integer.*/
O= unrank(N); say ' unrank=' O /*generate original integer and display*/
exit /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
rank: return x2d( translate( space( arg(1) ), 'c', ",") )
unrank: return space( translate( d2x( arg(1) ), ',', "C") )</syntaxhighlight>
{{out|output|text=&nbsp; when using the default input:}}
<pre>
original list= 3,14,159,265358979323846
map integer= 18594192178172074189223245894
unrank= 3,14,159,265358979323846
</pre>
 
=={{header|Ruby}}==
{{trans|Python}}
<langsyntaxhighlight lang="ruby">def rank(arr)
arr.join('a').to_i(11)
end
 
def unrank(n)
n.to_s(11).split('a').collect{|x| x.map(&:to_i})
end
 
Line 304 ⟶ 1,249:
p n
l = unrank(n)
p l</langsyntaxhighlight>
{{out}}
<pre>
Line 311 ⟶ 1,256:
[1, 2, 3, 10, 100, 987654321]
</pre>
=== Bijection ===
{{trans|Python}}
<syntaxhighlight 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))}"</syntaxhighlight>
{{out}}
<pre>
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]
</pre>
 
=={{header|Scala}}==
{{Out}}Best seen in running your browser either by [https://scalafiddle.io/sf/7NvnU4t/0 ScalaFiddle (ES aka JavaScript, non JVM)] or [https://scastie.scala-lang.org/l0uAGyyCTDSAV9Q45vRGaA Scastie (remote JVM)].
<syntaxhighlight lang="scala">object IndexFiniteList extends App {
val (defBase, s) = (10, Seq(1, 2, 3, 10, 100, 987654321))
 
def rank(x: Seq[Int], base: Int = defBase) =
BigInt(x.map(Integer.toString(_, base)).mkString(base.toHexString), base + 1)
 
def unrank(n: BigInt, base: Int = defBase): List[BigInt] =
n.toString(base + 1).split((base).toHexString).map(BigInt(_)).toList
 
val ranked = rank(s)
 
println(s.mkString("[", ", ", "]"))
println(ranked)
println(unrank(ranked).mkString("[", ", ", "]"))
 
}</syntaxhighlight>
 
=={{header|Sidef}}==
{{trans|Ruby}}
<syntaxhighlight lang="ruby">func rank(Array arr) {
Number(arr.join('a'), 11)
}
 
func unrank(Number n) {
n.base(11).split('a').map { Num(_) }
}
 
var l = [1, 2, 3, 10, 100, 987654321]
say l
var n = rank(l)
say n
var l = unrank(n)
say l</syntaxhighlight>
{{out}}
<pre>[1, 2, 3, 10, 100, 987654321]
14307647611639042485573
[1, 2, 3, 10, 100, 987654321]</pre>
 
'''Bijection:'''
<syntaxhighlight lang="ruby">func unrank(Number n) {
n == 1 ? [0]
: n.base(2).substr(1).split('0', -1).map{.len}
}
 
func rank(Array x) {
x.is_empty ? 0
: Number('1' + x.map { '1' * _ }.join('0'), 2)
}
 
for x in (0..10) {
printf("%3d : %-18s: %d\n", x, unrank(x), rank(unrank(x)))
}
 
say ''
var x = [1, 2, 3, 5, 8]
say "#{x} => #{rank(x)} => #{unrank(rank(x))}"</syntaxhighlight>
{{out}}
<pre> 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]</pre>
 
=={{header|Tcl}}==
{{works with|Tcl|8.6}}
Inspired by the [[#D|D solution]].
<langsyntaxhighlight lang="tcl">package require Tcl 8.6
 
proc rank {integers} {
Line 323 ⟶ 1,376:
proc unrank {codedValue} {
lmap i [split $codedValue 8] {scan $i %llo}
}</langsyntaxhighlight>
Demonstrating:
<langsyntaxhighlight 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"</langsyntaxhighlight>
{{out}}
<pre>
Line 336 ⟶ 1,389:
encoded: 1828381281448726746426183460251416730347660304377387
after: 1 2 3 10 100 987654321 135792468107264516704251 7
</pre>
 
=={{header|Wren}}==
{{trans|Kotlin}}
{{libheader|Wren-big}}
<syntaxhighlight lang="wren">import "./big" for BigInt
 
// Separates each integer in the list with an 'a' then encodes in base 11.
// Empty list mapped to '-1'.
var rank = Fn.new { |li|
if (li.count == 0) return BigInt.minusOne
return BigInt.fromBaseString(li.join("a"), 11)
}
 
var unrank = Fn.new { |r|
if (r == BigInt.minusOne) return []
return r.toBaseString(11).split("a").map { |d| (d != "") ? Num.fromString(d) : 0 }.toList
}
 
// Each integer n in the list mapped to '1' plus n '0's.
// Empty list mapped to '0'
var rank2 = Fn.new { |li|
if (li.isEmpty) return BigInt.zero
var sb = ""
for (i in li) sb = sb + "1" + ("0" * i)
return BigInt.fromBaseString(sb, 2)
}
 
var unrank2 = Fn.new { |r|
if (r == BigInt.zero) return []
return r.toBaseString(2)[1..-1].split("1").map { |d| d.count }.toList
}
 
var li = [0, 1, 2, 3, 10, 100, 987654321]
System.print("Before ranking : %(li)")
var r = rank.call(li)
System.print("Rank = %(r)")
li = unrank.call(r)
System.print("After unranking : %(li)")
System.print("\nAlternative approach (not suitable for large numbers)...\n")
li = li[0..-2]
System.print("Before ranking : %(li)")
r = rank2.call(li)
System.print("Rank = %(r)")
li = unrank2.call(r)
System.print("After unranking : %(li)")</syntaxhighlight>
 
{{out}}
<pre>
Before ranking : [0, 1, 2, 3, 10, 100, 987654321]
Rank = 828335141480036653618783
After unranking : [0, 1, 2, 3, 10, 100, 987654321]
 
Alternative approach (not suitable for large numbers)...
 
Before ranking : [0, 1, 2, 3, 10, 100]
Rank = 4364126777249122850009283661412696064
After unranking : [0, 1, 2, 3, 10, 100]
</pre>
 
=={{header|zkl}}==
Using GMP, base 11 and sometimes strings to represent big ints.
<syntaxhighlight 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") }</syntaxhighlight>
<syntaxhighlight 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);</syntaxhighlight>
{{out}}
<pre>
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")
</pre>
Peak
2,455

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/246815...352474"