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

10,446 bytes added ,  3 months ago
→‎{{header|jq}}: simplify
(→‎{{header|jq}}: simplify)
 
(26 intermediate revisions by 10 users not shown)
Line 24:
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 {
Line 48 ⟶ 101:
s.rank.writeln;
s.rank.unrank.writeln;
}</langsyntaxhighlight>
{{out}}
<pre>[1, 2, 3, 10, 100, 987654321]
Line 57 ⟶ 110:
=={{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.
<langsyntaxhighlight FreeBASIClang="freebasic">type duple
A as ulongint
B as ulongint
Line 149 ⟶ 202:
print R,
unrank R, X()
show_list(X())</langsyntaxhighlight>
{{out}}
<pre>0 []
Line 160 ⟶ 213:
 
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.
<langsyntaxhighlight lang="go">package main
 
import (
Line 198 ⟶ 251:
r := rank(u)
fmt.Printf("\n%v\n%d\n%d\n", &b, u, &r)
}</langsyntaxhighlight>
{{out}}
<pre>
Line 220 ⟶ 273:
 
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.
<langsyntaxhighlight lang="go">package main
 
import (
Line 312 ⟶ 365:
}
return l
}</langsyntaxhighlight>
{{out}}
<pre>
Line 329 ⟶ 382:
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}}==
Line 336 ⟶ 440:
Implementation:
 
<langsyntaxhighlight lang="j">scrunch=:3 :0
n=.1x+>./y
#.(1#~##:n),0,n,&#:n#.y
Line 346 ⟶ 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.
 
Whether this is an efficient representation or not depends, of course, on the nature of the list being represented.
 
 
=== Tacit versions ===
Line 366 ⟶ 469:
Base 11 encoding:
 
<langsyntaxhighlight lang="j"> rank =. 11&#.@:}.@:>@:(,&:>/)@:(<@:(10&,)@:(10&#.^:_1)"0)@:x:
unrank=. 10&#.;._1@:(10&,)@:(11&#.^:_1)</langsyntaxhighlight>
 
Example use:
 
<langsyntaxhighlight Jlang="j"> rank 1 2 3 10 100 987654321 135792468107264516704251 7x
187573177082615698496949025806128189691804770100426
unrank 187573177082615698496949025806128189691804770100426x
1 2 3 10 100 987654321 135792468107264516704251 7</langsyntaxhighlight>
 
Prime factorization (Gödelian) encoding:
 
<langsyntaxhighlight lang="j"> rank=. */@:(^~ p:@:i.@:#)@:>:@:x:
unrank=. <:@:(#;.1@:~:@:q:)</langsyntaxhighlight>
 
Example use:
 
<langsyntaxhighlight Jlang="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</langsyntaxhighlight>
 
=== Bijective ===
Line 394 ⟶ 497:
Using the method of the Python version (shifted):
 
<langsyntaxhighlight lang="j"> rank=. 1 -~ #.@:(1 , >@:(([ , 0 , ])&.>/)@:(<@:($&1)"0))@:x:
unrank=. #;._2@:((0 ,~ }.)@:(#.^:_1)@:(1&+))</langsyntaxhighlight>
 
Example use:
 
<langsyntaxhighlight Jlang="j"> >@:((] ; unrank ; rank@:unrank)&.>)@:i. 11
┌──┬───────┬──┐
│0 │0 │0 │
Line 427 ⟶ 530:
┌─────────┬────────┬─────────┐
│1 2 3 5 8│14401278│1 2 3 5 8│
└─────────┴────────┴─────────┘</langsyntaxhighlight>
 
=={{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}}
<langsyntaxhighlight lang="java">import java.math.BigInteger;
import static java.util.Arrays.stream;
import java.util.*;
Line 459 ⟶ 562:
System.out.println(unrank(rank(s)));
}
}</langsyntaxhighlight>
<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>
 
 
===Bijective map based on "n 0s" encoding===
<syntaxhighlight lang="jq">
### Infrastructure
 
# 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}}
 
<langsyntaxhighlight lang="julia">using LinearAlgebra
LinearAlgebra.rank(x::Vector{<:Integer}) = parse(BigInt, "1a" * join(x, 'a'), base=11)
function unrank(n::Integer)
Line 482 ⟶ 756:
n = rank(v)
v = unrank(n)
println("# v = $v\n -> n = $n\n -> v = $v")</langsyntaxhighlight>
 
{{out}}
Line 490 ⟶ 764:
 
=={{header|Kotlin}}==
<langsyntaxhighlight lang="scala">// version 1.1.2
 
import java.math.BigInteger
Line 543 ⟶ 817:
println("${"%2d".format(i)} -> ${li.toString().padEnd(9)} -> ${rank2(li)}")
}
}</langsyntaxhighlight>
 
{{out}}
Line 571 ⟶ 845:
 
=={{header|Mathematica}} / {{header|Wolfram Language}}==
<langsyntaxhighlight Mathematicalang="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]</langsyntaxhighlight>
{{out}}
<pre>4886947482322057719812858634706703
Line 585 ⟶ 859:
{{trans|Go}}
{{libheader|bignum}}
<langsyntaxhighlight Nimlang="nim">import strformat, strutils
import bignum
 
Line 615 ⟶ 889:
let u = b.unrank()
let r = u.rank()
echo &"\n{b}\n{u}\n{r}"</langsyntaxhighlight>
 
{{out}}
Line 638 ⟶ 912:
{{trans|Raku}}
{{libheader|ntheory}}
<langsyntaxhighlight lang="perl">use bigint;
use ntheory qw(fromdigits todigitstring);
use feature 'say';
Line 647 ⟶ 921:
say join ' ', @n = qw<12 11 0 7 9 15 15 5 7 13 5 5>;
say $n = rank(@n);
say join ' ', unrank $n;</langsyntaxhighlight>
{{out}}
<pre>12 11 0 7 9 15 15 5 7 13 5 5
Line 656 ⟶ 930:
===base 11===
{{trans|Sidef}}
{{libheader|Phix/mpfr}}
<!--<lang Phix>-->
Note this is ''not'' supported under pwa/p2js because mpz_set_str() currently only handles bases 2, 8, 10, and 16.
<span style="color: #008080;">include</span> <span style="color: #7060A8;">mpfr</span><span style="color: #0000FF;">.</span><span style="color: #000000;">e</span>
<!--<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: #7060A8004080;">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: #0000007060A8;">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: #7060A8004080;">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>
Line 675 ⟶ 953:
<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: #7060A8004080;">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>
<!--</langsyntaxhighlight>-->
{{out}}
<pre>
Line 687 ⟶ 965:
===bijective===
{{trans|Python}}
<!--<langsyntaxhighlight Phixlang="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>
Line 697 ⟶ 976:
<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: #008000000000;">"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;">xy</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;">xy</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>
Line 712 ⟶ 992:
<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>
<!--</langsyntaxhighlight>-->
{{out}}
<pre>
Line 730 ⟶ 1,010:
 
=={{header|Python}}==
<langsyntaxhighlight lang="python">def rank(x): return int('a'.join(map(str, [1] + x)), 11)
 
def unrank(n):
Line 742 ⟶ 1,022:
print n
l = unrank(n)
print l</langsyntaxhighlight>
{{out}}
<pre>
Line 752 ⟶ 1,032:
=== 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.
<langsyntaxhighlight lang="python">def unrank(n):
return map(len, bin(n)[3:].split("0")) if n else []
 
Line 764 ⟶ 1,044:
x = [1, 2, 3, 5, 8];
print x, rank(x), unrank(rank(x))
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 781 ⟶ 1,061:
[1, 2, 3, 5, 8] 14401279 [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}}==
Line 786 ⟶ 1,109:
{{trans|Tcl}} (which gives credit to [[#D]])
 
<langsyntaxhighlight lang="racket">#lang racket/base
(require (only-in racket/string string-join string-split))
 
Line 807 ⟶ 1,130:
(displayln loi)
(displayln rnk)
(displayln urk))</langsyntaxhighlight>
 
{{out}}
Line 818 ⟶ 1,141:
(formerly Perl 6)
Here is a cheap solution using a base-11 encoding and string operations:
<syntaxhighlight lang="raku" perl6line>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;</langsyntaxhighlight>
{{out}}
<pre>1 11 16 1 3 9 0 2 15 7 19 10
Line 831 ⟶ 1,154:
Here is a bijective solution that does not use string operations.
 
<syntaxhighlight lang="raku" perl6line>multi infix:<rad> () { 0 }
multi infix:<rad> ($a) { $a }
multi infix:<rad> ($a, $b) { $a * $*RADIX + $b }
Line 871 ⟶ 1,194:
my @unrank = unrank $_;
say "$_ -> [$@unrank] -> {rank @unrank}";
}</langsyntaxhighlight>
 
{{out}}
Line 890 ⟶ 1,213:
 
No checks are made that the numbers are non-negative integers or malformed integers.
<langsyntaxhighlight 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.*/
Line 903 ⟶ 1,226:
/*──────────────────────────────────────────────────────────────────────────────────────*/
rank: return x2d( translate( space( arg(1) ), 'c', ",") )
unrank: return space( translate( d2x( arg(1) ), ',', "C") )</langsyntaxhighlight>
{{out|output|text=&nbsp; when using the default input:}}
<pre>
Line 913 ⟶ 1,236:
=={{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 926 ⟶ 1,249:
p n
l = unrank(n)
p l</langsyntaxhighlight>
{{out}}
<pre>
Line 935 ⟶ 1,258:
=== Bijection ===
{{trans|Python}}
<langsyntaxhighlight lang="ruby">def unrank(n)
return [0] if n==1
n.to_s(2)[1..-1].split('0',-1).map(&:size)
Line 951 ⟶ 1,274:
puts
x = [1, 2, 3, 5, 8]
puts "#{x} => #{rank(x)} => #{unrank(rank(x))}"</langsyntaxhighlight>
{{out}}
<pre>
Line 971 ⟶ 1,294:
=={{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)].
<langsyntaxhighlight Scalalang="scala">object IndexFiniteList extends App {
val (defBase, s) = (10, Seq(1, 2, 3, 10, 100, 987654321))
 
Line 986 ⟶ 1,309:
println(unrank(ranked).mkString("[", ", ", "]"))
 
}</langsyntaxhighlight>
 
=={{header|Sidef}}==
{{trans|Ruby}}
<langsyntaxhighlight lang="ruby">func rank(Array arr) {
Number(arr.join('a'), 11)
}
Line 1,003 ⟶ 1,326:
say n
var l = unrank(n)
say l</langsyntaxhighlight>
{{out}}
<pre>[1, 2, 3, 10, 100, 987654321]
Line 1,010 ⟶ 1,333:
 
'''Bijection:'''
<langsyntaxhighlight lang="ruby">func unrank(Number n) {
n == 1 ? [0]
: n.base(2).substr(1).split('0', -1).map{.len}
Line 1,026 ⟶ 1,349:
say ''
var x = [1, 2, 3, 5, 8]
say "#{x} => #{rank(x)} => #{unrank(rank(x))}"</langsyntaxhighlight>
{{out}}
<pre> 0 : [] : 0
Line 1,045 ⟶ 1,368:
{{works with|Tcl|8.6}}
Inspired by the [[#D|D solution]].
<langsyntaxhighlight lang="tcl">package require Tcl 8.6
 
proc rank {integers} {
Line 1,053 ⟶ 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 1,071 ⟶ 1,394:
{{trans|Kotlin}}
{{libheader|Wren-big}}
<langsyntaxhighlight ecmascriptlang="wren">import "./big" for BigInt
 
// Separates each integer in the list with an 'a' then encodes in base 11.
Line 1,111 ⟶ 1,434:
System.print("Rank = %(r)")
li = unrank2.call(r)
System.print("After unranking : %(li)")</langsyntaxhighlight>
 
{{out}}
Line 1,128 ⟶ 1,451:
=={{header|zkl}}==
Using GMP, base 11 and sometimes strings to represent big ints.
<langsyntaxhighlight 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") }</langsyntaxhighlight>
<langsyntaxhighlight lang="zkl">fcn rankz(ns,S=False){
ns.println();
rank(ns).println();
Line 1,139 ⟶ 1,462:
}
rankz(T(1,2,3,10,100,987654321));
rankz(T(1,2,3,10,100,987654321,"135792468107264516704251",7),True);</langsyntaxhighlight>
{{out}}
<pre>
Peak
2,442

edits

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