Index finite lists of positive integers: Difference between revisions

{{trans|Python}}

R BigInt(([1] [+] x).map(String).join(‘A’), radix' 11)

print(n)

l = unrank(n)

{{out}}

=={{header|Arturo}}==

if empty? arr -> return 0

from.binary "1" ++ join.with:"0" map arr 'a -> repeat "1" a

u: unrank r

{{out}}

This solution isn't efficient.

{{trans|Python}}

BigInt rank(T)(in T[] x) pure /*nothrow*/ @safe {

s.rank.writeln;

s.rank.unrank.writeln;

{{out}}

<pre>[1, 2, 3, 10, 100, 987654321]

=={{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.

A as ulongint

B as ulongint

print R,

unrank R, X()

{{out}}

<pre>0 []

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.

import (

r := rank(u)

fmt.Printf("\n%v\n%d\n%d\n", &b, u, &r)

{{out}}

<pre>

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.

import (

}

return l

{{out}}

<pre>

=={{header|Haskell}}==

toBase :: Int -> Integer -> [Int]

go 0 [] = []

go i (0:xs) = go (i+1) xs

Using different bases we may enumerate lists.

Implementation:

n=.1x+>./y

#.(1#~##:n),0,n,&#:n#.y

n=.#.m{.(m+1)}.b

n #.inv#.(1+2*m)}.b

Example use:

4314664669630761

hcnurcs 4314664669630761

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.

Base 11 encoding:

Example use:

187573177082615698496949025806128189691804770100426

unrank 187573177082615698496949025806128189691804770100426x

Prime factorization (Gödelian) encoding:

Example use:

6857998574998940803374702726455974765530187550029640884386375715876970128518999225074067307280381624132537960815429687500

unrank 6857998574998940803374702726455974765530187550029640884386375715876970128518999225074067307280381624132537960815429687500x

=== Bijective ===

Using the method of the Python version (shifted):

Example use:

┌──┬───────┬──┐

│0 │0 │0 │

┌─────────┬────────┬─────────┐

│1 2 3 5 8│14401278│1 2 3 5 8│

=={{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}}

import static java.util.Arrays.stream;

import java.util.*;

System.out.println(unrank(rank(s)));

}

<pre>[1, 2, 3, 10, 100, 987654321]

37699814998383067155219233

{{trans|Python}}

LinearAlgebra.rank(x::Vector{<:Integer}) = parse(BigInt, "1a" * join(x, 'a'), base=11)

function unrank(n::Integer)

n = rank(v)

v = unrank(n)

{{out}}

=={{header|Kotlin}}==

import java.math.BigInteger

println("${"%2d".format(i)} -> ${li.toString().padEnd(9)} -> ${rank2(li)}")

}

{{out}}

=={{header|Mathematica}} / {{header|Wolfram Language}}==

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[%]

{{out}}

<pre>4886947482322057719812858634706703

{{trans|Go}}

{{libheader|bignum}}

import bignum

let u = b.unrank()

let r = u.rank()

{{out}}

{{trans|Raku}}

{{libheader|ntheory}}

use ntheory qw(fromdigits todigitstring);

use feature 'say';

say join ' ', @n = qw<12 11 0 7 9 15 15 5 7 13 5 5>;

say $n = rank(@n);

{{out}}

<pre>12 11 0 7 9 15 15 5 7 13 5 5

{{libheader|Phix/mpfr}}

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;">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: #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>

{{out}}

<pre>

===bijective===

{{trans|Python}}

<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;">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>

{{out}}

<pre>

=={{header|Python}}==

def unrank(n):

print n

l = unrank(n)

{{out}}

<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', then taken as a binary number. Empty list is mapped to 0 as a special case. Don't use it on large numbers.

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

x = [1, 2, 3, 5, 8];

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

{{out}}

<pre>

=={{header|Quackery}}==

witheach

[ number$

else join ]

drop ] is unrank ( n --> [ )

{{out}}

{{trans|Tcl}} (which gives credit to [[#D]])

(require (only-in racket/string string-join string-split))

(displayln loi)

(displayln rnk)

{{out}}

(formerly Perl 6)

Here is a cheap solution using a base-11 encoding and string operations:

sub unrank(Int $n) { $n.base(11).split('A') }

say my @n = (1..20).roll(12);

say my $n = rank(@n);

{{out}}

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

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

multi infix:<rad> ($a) { $a }

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

my @unrank = unrank $_;

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

{{out}}

No checks are made that the numbers are non-negative integers or malformed integers.

parse arg $ /*obtain optional argument (int list).*/

if $='' | $="," then $=3 14 159 265358979323846 /*Not specified? Then use the default.*/

/*──────────────────────────────────────────────────────────────────────────────────────*/

rank: return x2d( translate( space( arg(1) ), 'c', ",") )

{{out|output|text=&nbsp; when using the default input:}}

<pre>

=={{header|Ruby}}==

{{trans|Python}}

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

end

p n

l = unrank(n)

{{out}}

<pre>

=== Bijection ===

{{trans|Python}}

return [0] if n==1

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

puts

x = [1, 2, 3, 5, 8]

{{out}}

<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)].

val (defBase, s) = (10, Seq(1, 2, 3, 10, 100, 987654321))

println(unrank(ranked).mkString("[", ", ", "]"))

=={{header|Sidef}}==

{{trans|Ruby}}

Number(arr.join('a'), 11)

}

say n

var l = unrank(n)

{{out}}

<pre>[1, 2, 3, 10, 100, 987654321]

'''Bijection:'''

n == 1 ? [0]

: n.base(2).substr(1).split('0', -1).map{.len}

say ''

var x = [1, 2, 3, 5, 8]

{{out}}

<pre> 0 : [] : 0

{{works with|Tcl|8.6}}

Inspired by the [[#D|D solution]].

proc rank {integers} {

proc unrank {codedValue} {

lmap i [split $codedValue 8] {scan $i %llo}

Demonstrating:

puts "prior: $s"

set c [rank $s]

puts "encoded: $c"

set t [unrank $c]

{{out}}

<pre>

{{trans|Kotlin}}

{{libheader|Wren-big}}

// Separates each integer in the list with an 'a' then encodes in base 11.

System.print("Rank = %(r)")

li = unrank2.call(r)

{{out}}

=={{header|zkl}}==

Using GMP, base 11 and sometimes strings to represent big ints.

fcn rank(ns) { BN(ns.concat("A"),11) }

fcn unrank(bn) { bn.toString(11).split("a").apply("toInt") }

ns.println();

rank(ns).println();

}

rankz(T(1,2,3,10,100,987654321));

{{out}}

<pre>