Rosetta Code

Permutations/Rank of a permutation: Difference between revisions

Page Discussion

Permutations/Rank of a permutation (view source)

Revision as of 12:48, 24 January 2024

5,940 bytes added ,  4 months ago
m
→‎{{header|Wren}}: Minor tidy
(Added 11l)
m (→‎{{header|Wren}}: Minor tidy)
(7 intermediate revisions by 5 users not shown)
Line 60:
{{trans|Nim}}
 
<langsyntaxhighlight lang="11l">UInt32 seed = 0
F nonrandom()
:seed = 1664525 * :seed + 1013904223
Line 103:
print()
V tv12 = [0] * 12
L(i) 4
V r = Int(nonrandom() * factorial(12))
getPermutation(&tv12, r)
print(‘#9 -> #. -> #.’.format(r, tv12, getRank(tv12)))</langsyntaxhighlight>
 
{{out}}
Line 151:
=== C: Myrvold and Ruskey ===
This is algorithm #1 from the M&R paper.
<langsyntaxhighlight lang="c">#include <stdio.h>
#include <stdlib.h>
 
Line 219:
}
}
</syntaxhighlight>
</lang>
 
{{out}}
Line 246:
22: [ 0, 1, 3, 2 ] = 22
23: [ 0, 1, 2, 3 ] = 23
</pre>
 
=={{header|C++}}==
<syntaxhighlight lang="c++">
#include <cstdint>
#include <iostream>
#include <random>
#include <vector>
 
void print_vector(const std::vector<int32_t>& list) {
std::cout << "[";
for ( uint64_t i = 0; i < list.size() - 1; ++i ) {
std::cout << list[i] << ", ";
}
std::cout << list.back() << "]";
}
 
uint64_t factorial(const int32_t& n) {
uint64_t factorial = 1;
for ( int32_t i = 2; i <= n; ++i ) {
factorial *= i;
}
return factorial;
}
 
uint64_t rank1(const int32_t& n, std::vector<int32_t>& vec, std::vector<int32_t>& inverse) {
if ( n < 2 ) {
return 0;
}
 
const int32_t last = vec[n - 1];
std::swap(vec[n - 1], vec[inverse[n - 1]]);
std::swap(inverse[last], inverse[n - 1]);
return last + n * rank1(n - 1, vec, inverse);
}
 
void unrank1(const int64_t& rank, const int32_t& n, std::vector<int32_t>& vec) {
if ( n < 1 ) {
return;
}
 
const int64_t quotient = rank / n;
const int64_t remainder = rank % n;
std::swap(vec[remainder], vec[n - 1]);
unrank1(quotient, n - 1, vec);
}
 
int64_t rank(const int32_t& n, std::vector<int32_t>& vec) {
std::vector<int32_t> copy_vec(n, 0);
std::vector<int32_t> inverse(n, 0);
for ( int32_t i = 0; i < n; ++i ) {
copy_vec[i] = vec[i];
inverse[vec[i]] = i;
}
return rank1(n, copy_vec, inverse);
}
 
void permutation(const int64_t& rank, const int32_t& n, std::vector<int32_t>& vec) {
std::iota(vec.begin(), vec.end(), 0);
unrank1(rank, n, vec);
}
 
int main() {
int32_t test_size = 3;
std::vector<int32_t> test_vector(test_size, 0);
for ( uint64_t count = 0; count < factorial(test_size); ++count ) {
permutation(count, test_size, test_vector);
std::cout << count << " -> ";
print_vector(test_vector);
std::cout << " -> " << rank(3, test_vector) << std::endl;
}
std::cout << std::endl;
 
test_size = 12; // test_size can be increased up to a maximum of 20
test_vector.resize(test_size);
 
std::random_device random;
std::mt19937 generator(random());
std::uniform_real_distribution<double> distribution(0.0F, 1.0F);
 
for ( int32_t count = 0; count < 4; ++count ) {
const uint64_t rand = distribution(generator) * factorial(test_size);
permutation(rand, test_size, test_vector);
std::cout << rand << " -> ";
print_vector(test_vector);
std::cout << " -> " << rank(test_size, test_vector) << std::endl;
}
}
</syntaxhighlight>
{{ out }}
<pre>
0 -> [1, 2, 0] -> 0
1 -> [2, 0, 1] -> 1
2 -> [1, 0, 2] -> 2
3 -> [2, 1, 0] -> 3
4 -> [0, 2, 1] -> 4
5 -> [0, 1, 2] -> 5
 
247958875 -> [9, 1, 10, 5, 2, 0, 4, 11, 8, 6, 3, 7] -> 247958875
115652888 -> [10, 9, 4, 1, 3, 6, 5, 7, 0, 11, 2, 8] -> 115652888
353180282 -> [7, 5, 4, 1, 3, 10, 6, 0, 9, 8, 11, 2] -> 353180282
275422075 -> [2, 4, 10, 1, 3, 5, 8, 11, 6, 0, 9, 7] -> 275422075
</pre>
 
Line 251 ⟶ 353:
{{trans|C}}
Currently this doesn't use BigInts.
<langsyntaxhighlight lang="d">import std.stdio, std.algorithm, std.range;
 
alias TRank = ulong;
Line 313 ⟶ 415:
writefln("%20d: %s = %d", rank, items2, items2.computeRank);
}
}</langsyntaxhighlight>
{{out}}
<pre> 0: [1, 2, 3, 0] = 0
Line 348 ⟶ 450:
=={{header|FreeBASIC}}==
===Up to 20 objects===
<langsyntaxhighlight lang="freebasic">' version 31-03-2017
' compile with: fbc -s console
 
Line 497 ⟶ 599:
Print : Print "hit any key to end program"
Sleep
End</langsyntaxhighlight>
{{out}}
<pre>Rank: unrank1 rank1
Line 532 ⟶ 634:
===Using GMP for the big numbers===
{{libheader|GMP}}
<langsyntaxhighlight lang="freebasic">' version 31-03-2017
' compile with: fbc -s console
 
Line 648 ⟶ 750:
Print : Print "hit any key to end program"
Sleep
End</langsyntaxhighlight>
{{out}}
<pre>862993243747395020367391904490190117106585269146708404403331561502140758428008657463653366643611155380240799622282374456087743515643868809722278635878978733132591027133490410275442362000562723356064257191755491520940533177124123076535632269113257248
Line 669 ⟶ 771:
 
=={{header|Go}}==
<langsyntaxhighlight lang="go">package main
 
import (
Line 750 ⟶ 852:
fmt.Println(r, MRPerm(r, n))
}
}</langsyntaxhighlight>
{{out}}
<pre>
Line 769 ⟶ 871:
=={{header|Haskell}}==
Without the random part.
<langsyntaxhighlight lang="haskell">fact :: Int -> Int
fact n = product [1 .. n]
 
Line 788 ⟶ 890:
f n = print (n, p, permRank p)
where
p = rankPerm [0 .. 3] n</langsyntaxhighlight>
{{out}}
from rank to permutation back to rank:
Line 821 ⟶ 923:
The J primitive <code>A.</code> provides an effective solution to this task. Generating 4 random permutations of 144 items takes about 6 milliseconds so solving the Stack Overflow question ought to take about 100 minutes on that particular test machine.
 
<langsyntaxhighlight lang="j"> A. 2 0 1 NB. return rank of permutation
4
4 A. i.3 NB. return permutation of rank 4
Line 845 ⟶ 947:
111 65 136 58 92 46 4 83 20 54 21 10 72 110 56 28 13 18 73 133 105 117 63 126 114 43 5 80 45 88 86 108 11 29 0 129 71 141 59 53 113 137 2 102 95 15 35 74 107 61 134 36 32 19 106 100 55 69 76 142 64 49 9 30 47 123 12 97 42...
64 76 139 122 37 127 57 143 32 108 46 17 126 9 51 59 1 74 23 89 42 124 132 19 93 137 70 86 14 112 83 91 63 39 73 18 90 120 53 103 140 87 43 55 131 40 142 102 107 111 80 65 61 34 66 75 88 92 13 138 50 117 97 20 44 7 56 94 41...
139 87 98 118 125 65 35 112 10 43 85 66 58 131 36 30 50 11 136 130 71 100 79 142 40 69 101 84 143 33 95 26 18 94 13 68 8 0 47 70 129 48 107 64 93 16 83 39 29 81 6 105 78 92 104 60 15 55 4 14 7 91 86 12 31 46 20 133 53...</langsyntaxhighlight>
 
=={{header|Java}}==
Line 855 ⟶ 957:
'''Code:'''
 
<langsyntaxhighlight lang="java">import java.math.BigInteger;
import java.util.*;
 
Line 926 ⟶ 1,028:
}
}</langsyntaxhighlight>
 
{{out}}
Line 954 ⟶ 1,056:
 
'''Preliminaries'''
<langsyntaxhighlight lang="jq"># Assuming sufficiently-precise integer arithmetic,
# if the input and $j are integers, then the result will be a pair of integers,
# except that if $j is 0, then an error condition is raised.
Line 972 ⟶ 1,074:
| reduce range(2; $n) as $i ($n; . * $i);
 
def lpad($len): tostring | ($len - length) as $l | (" " * $l)[:$l] + .;</langsyntaxhighlight>
 
'''The Tasks'''
<langsyntaxhighlight lang="jq"># Myrvold and Ruskey algorithm
# The input should be a permutation of 0 ... $n-1 inclusive
def mrUnrank1($rank; $n):
Line 1,026 ⟶ 1,128:
task(4),
"",
task3</langsyntaxhighlight>
{{out}}
<pre>
Line 1,078 ⟶ 1,180:
 
Unfortunately, as of the 0.3 release of Julian, this code can not be used to address the StackOverflow question. Although many of Julia's permutation built-in functions support large permutations, <tt>nthperm(p)</tt> is limited to partitions of no more than 20 objects. <tt>p = randperm(114)</tt> works fine, but <tt>nthperm(p)</tt> throws an <tt>OverflowError</tt>. Arguably, this is a bug, and it may be rectified in future releases.
<langsyntaxhighlight Julialang="julia">using Printf
 
nobjs = 4
Line 1,105 ⟶ 1,207:
println(" ", p, " (", prank, ")")
end
</syntaxhighlight>
</lang>
 
{{out}}
Line 1,144 ⟶ 1,246:
=={{header|Kotlin}}==
{{trans|C}}
<langsyntaxhighlight lang="scala">// version 1.1.2
 
import java.util.Random
Line 1,208 ⟶ 1,310:
System.out.printf("%9d -> %s -> %d\n", r, tv.contentToString(), getRank(12, tv))
}
}</langsyntaxhighlight>
 
{{out}}
Line 1,252 ⟶ 1,354:
=={{header|Mathematica}}/{{header|Wolfram Language}}==
{{trans|Haskell}}
<langsyntaxhighlight lang="mathematica">fromrank[list_, 0] := list;
fromrank[list_, n_] :=
Prepend[fromrank[DeleteCases[list, #],
Line 1,265 ⟶ 1,367:
 
Do[Print@fromrank[Range[0, 12 - 1], RandomInteger[12!]], {4}];
Do[Print@fromrank[Range[0, 144 - 1], RandomInteger[144!]], {4}];</langsyntaxhighlight>
{{Out}}
<pre>{0,{0,1,2,3},0}
Line 1,302 ⟶ 1,404:
=={{header|Nim}}==
{{trans|Kotlin}}
<langsyntaxhighlight Nimlang="nim">func mrUnrank1(vec: var openArray[int]; rank, n: int) =
if n < 1: return
let q = rank div n
Line 1,349 ⟶ 1,451:
for r in newSeqWith(4, rand(fac(12))):
tv12.getPermutation(r)
echo &"{r:>9} → {tv12} → {tv12.getRank()}"</langsyntaxhighlight>
 
{{out}}
Line 1,391 ⟶ 1,493:
=={{header|PARI/GP}}==
The functions are built into GP already: <code>numtoperm</code> and <code>permtonum</code>
<langsyntaxhighlight lang="parigp">vector(3!,i,permtonum(numtoperm(3,i-1)))==vector(3!,i,i-1)
vector(4,i,numtoperm(12,random(12!)))
for(i=1,1e6,numtoperm(144,random(144!)))</langsyntaxhighlight>
{{out}}
<pre>%1 = 1
Line 1,401 ⟶ 1,503:
The ntheory module gives us <code>numtoperm</code> and <code>permtonum</code> commands similar to Pari/GP, though in the preferred lexicographic order. Values larger than the native int size are handled as well. The <code>randperm</code> function is useful for random permutations, using a Knuth shuffle and a Chacha/20 CSPRNG supplying randomness. A Macbook takes a bit under 4 seconds to generate 1 million random permutations of 144 objects, or 8 seconds if inserting into a set to ensure uniqueness.
{{libheader|ntheory}}
<langsyntaxhighlight lang="perl">use ntheory qw/:all/;
 
my $n = 3;
Line 1,421 ⟶ 1,523:
print " Four 4-object random permutations of 100k objects using randperm\n";
print join(" ", randperm(100000,4)),"\n" for 1..4;
</syntaxhighlight>
</lang>
 
{{out}}
Line 1,454 ⟶ 1,556:
=={{header|Phix}}==
{{trans|C}}
<!--<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;">get_rank</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">l</span><span style="color: #0000FF;">)</span>
Line 1,486 ⟶ 1,588:
<span style="color: #0000FF;">?</span><span style="color: #7060A8;">permute</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">rand</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">factorial</span><span style="color: #0000FF;">(</span><span style="color: #000000;">12</span><span style="color: #0000FF;">)),</span><span style="color: #000000;">l</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<!--</langsyntaxhighlight>-->
{{out}}
<pre>
Line 1,515 ⟶ 1,617:
Their algorithm is efficient and pythons transparent use of arbitrary precision integers allows the Stack Overflow questions limits to be used. (Chopped at four rather than a million random samples although function get_random_ranks(144, 1e6) doesn't take long).
 
<langsyntaxhighlight lang="python">from math import factorial as fact
from random import randrange
from textwrap import wrap
Line 1,600 ⟶ 1,702:
test1('First ordering:', unranker1, ranker1)
test1('Second ordering:', unranker2, ranker2)
test2('First ordering, large number of perms:', unranker1)</langsyntaxhighlight>
 
{{out}}
Line 1,674 ⟶ 1,776:
Permutations with small differences in rank are likely to be "similar" in appearance (if rank difference << perm length).
 
<langsyntaxhighlight lang="python">from random import randrange
from typing import List
 
Line 1,777 ⟶ 1,879:
rank = tj_rank(p)
parity = tj_parity(p)
print(f" Rank: {r:10} to perm: {p}, parity: {parity} to rank: {rank:10}")</langsyntaxhighlight>
 
{{out}}
Line 1,798 ⟶ 1,900:
Rank: 1651131773176615172744310076827657815133816254912906616309984015339196892250696046235920824910965887990997355014521316450705028487598467582997576624750079968277864250809611544676914954500478455362854192561093676053999830054190363254701022398791125041 to perm: [59, 73, 41, 108, 64, 40, 98, 4, 65, 67, 126, 88, 76, 29, 110, 70, 54, 122, 0, 7, 92, 10, 139, 141, 137, 37, 131, 119, 94, 18, 143, 129, 42, 95, 136, 20, 8, 74, 96, 113, 63, 85, 55, 115, 61, 116, 2, 22, 17, 124, 72, 128, 66, 86, 15, 123, 47, 32, 118, 112, 71, 24, 44, 69, 105, 49, 39, 9, 19, 107, 121, 97, 57, 114, 77, 51, 52, 56, 142, 68, 13, 109, 101, 27, 117, 60, 16, 106, 91, 45, 111, 79, 35, 33, 75, 135, 89, 34, 26, 134, 62, 125, 120, 38, 31, 102, 12, 93, 130, 43, 14, 90, 46, 50, 127, 99, 103, 1, 48, 84, 87, 133, 25, 104, 5, 6, 23, 3, 83, 100, 80, 58, 138, 132, 140, 81, 21, 53, 36, 78, 11, 82, 30, 28], parity: 1 to rank: 1651131773176615172744310076827657815133816254912906616309984015339196892250696046235920824910965887990997355014521316450705028487598467582997576624750079968277864250809611544676914954500478455362854192561093676053999830054190363254701022398791125041
Rank: 1139027037513751332871831142078907765417112324514533855069759708279338770804249106066012939576097376526053338448990932324347478214081719932920707580823619461100977982441090762742918774404245754930272491547901228595855393218252364279122306190572350742 to perm: [16, 104, 135, 22, 134, 88, 112, 141, 76, 86, 29, 11, 82, 28, 87, 57, 92, 73, 77, 46, 43, 137, 65, 54, 58, 125, 40, 83, 108, 18, 84, 60, 133, 99, 48, 98, 62, 55, 37, 70, 66, 91, 126, 113, 90, 45, 118, 89, 69, 68, 115, 117, 4, 53, 3, 21, 5, 33, 105, 95, 36, 0, 85, 27, 78, 142, 101, 94, 39, 131, 138, 120, 121, 41, 67, 136, 109, 32, 2, 128, 52, 8, 96, 44, 139, 132, 81, 123, 122, 129, 75, 35, 114, 59, 102, 12, 10, 93, 124, 56, 34, 50, 80, 7, 140, 38, 49, 6, 127, 24, 42, 106, 71, 97, 116, 23, 15, 30, 103, 20, 51, 143, 14, 1, 107, 64, 130, 9, 47, 17, 72, 19, 13, 119, 74, 79, 61, 111, 110, 26, 100, 25, 31, 63], parity: 0 to rank: 1139027037513751332871831142078907765417112324514533855069759708279338770804249106066012939576097376526053338448990932324347478214081719932920707580823619461100977982441090762742918774404245754930272491547901228595855393218252364279122306190572350742
Rank: 714995631345946967042806483133964554958984960300330719707047323701281032269403416575046138945880520006134289348162836428854957729363688052297494097936794838200697086588398613171177193379516938048929841183345138224064281691610834904263581078991507944 to perm: [53, 123, 58, 38, 126, 23, 43, 137, 18, 42, 118, 107, 130, 68, 31, 84, 11, 4, 125, 83, 122, 117, 82, 12, 59, 94, 90, 112, 98, 104, 124, 128, 120, 88, 91, 93, 6, 108, 115, 143, 44, 56, 73, 136, 14, 134, 54, 105, 7, 16, 97, 127, 9, 66, 37, 113, 3, 67, 102, 57, 106, 76, 19, 100, 49, 101, 74, 96, 95, 32, 35, 77, 142, 103, 70, 141, 135, 72, 129, 65, 46, 89, 51, 25, 40, 131, 24, 5, 21, 34, 10, 99, 55, 71, 114, 139, 87, 75, 64, 133, 45, 63, 48, 132, 29, 92, 22, 86, 20, 41, 33, 85, 138, 17, 0, 28, 119, 36, 79, 111, 80, 116, 30, 15, 61, 60, 1, 52, 121, 2, 62, 69, 13, 109, 78, 81, 110, 47, 26, 39, 27, 140, 50, 8], parity: 0 to rank: 714995631345946967042806483133964554958984960300330719707047323701281032269403416575046138945880520006134289348162836428854957729363688052297494097936794838200697086588398613171177193379516938048929841183345138224064281691610834904263581078991507944</prrepre>
 
===Python: Trotter-Johnson, Iterative===
Functions ranker1 and ranker2 above, can be changed from the recursive form as used in the paper to iterative versions if they are replaced with the following code that yields the same results:
 
<lang python>def ranker1(n, pi, pi1):
<syntaxhighlight lang="python">def ranker1(n, pi, pi1):
if n == 1:
return 0
Line 1,818 ⟶ 1,921:
pi1[s], pi1[i] = pi1[i], pi1[s]
result += s * fact(i)
return result</langsyntaxhighlight>
 
=={{header|Quackery}}==
 
Stretch goal: The words defined here would handle the limitations of the Stack Exchange question with ease, as Quackery numbers are BigInts. The only inconvenience would be generating random numbers in the range 0 to 144! - 1(*), as the built-in PRNG is limited to 64 bits.
 
(*) This would generate an arbitrary permutation of the numbers 0 to 143, <code>144 identity shuffle</code>. You ''could'' use that permutation to generate a number in the range 0 to 144! - 1 with <code>perm->rank</code> but it has a whiff of circular reasoning. <shrug>
 
<syntaxhighlight lang="Quackery">
[ 1 swap times [ i 1+ * ] ] is ! ( n --> n )
 
[ [] swap times [ i^ join ] ] is identity ( n --> [ )
 
[ dup identity unrot
[] unrot 1 - times
[ i 1+ ! /mod
dip join ] drop ] is factoradic ( n n --> [ )
 
[ [] unrot witheach
[ pluck
rot swap nested join
swap ]
join ] is inversion ( [ [ --> [ )
 
[ factoradic inversion ] is rank->perm ( n n --> [ )
 
[ [] over size identity
rot witheach
[ over find
dup dip
[ pluck drop ]
swap dip join ]
drop -1 split drop ] is perm->fdic ( [ --> [ )
 
[ 0 swap
witheach [ + i 1+ * ] ] is fdic->rank ( [ --> n )
 
[ perm->fdic fdic->rank ] is perm->rank ( [ --> n )
 
3 ! times
[ i^
dup echo say " -> "
3 rank->perm
dup echo say " -> "
perm->rank
echo cr ]
cr
4 times
[ 12 ! random
dup echo say " -> "
12 rank->perm
dup echo say " -> "
perm->rank
echo cr ]</syntaxhighlight>
 
{{out}}
 
<pre>0 -> [ 0 1 2 ] -> 0
1 -> [ 0 2 1 ] -> 1
2 -> [ 1 0 2 ] -> 2
3 -> [ 1 2 0 ] -> 3
4 -> [ 2 0 1 ] -> 4
5 -> [ 2 1 0 ] -> 5
 
195266704 -> [ 4 10 9 0 11 3 7 5 6 8 1 2 ] -> 195266704
240729875 -> [ 6 0 4 5 7 11 1 3 8 10 9 2 ] -> 240729875
109569601 -> [ 2 9 1 11 6 0 3 4 5 7 10 8 ] -> 109569601
275654445 -> [ 6 10 11 5 7 2 3 1 9 4 8 0 ] -> 275654445
</pre>
 
=={{header|Racket}}==
Mimicking the Haskell style.
<langsyntaxhighlight lang="racket">
#lang racket (require math)
(define-syntax def (make-rename-transformer #'match-define-values))
Line 1,838 ⟶ 2,009:
(* (for/sum ([x xs] #:when (< x x0)) 1)
(factorial (length xs))))]))
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 1,877 ⟶ 2,048:
It is easy generate random inversion vector without BigInt.
 
<syntaxhighlight lang="raku" perl6line>use v6;
 
sub rank2inv ( $rank, $n = * ) {
Line 1,926 ⟶ 2,097:
.say
};
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 1,959 ⟶ 2,130:
Since this REXX program generates permutations without recursive calls,
testing for the limit for a &nbsp; ''stack overflow'' &nbsp; wouldn't be necessary using this REXX program.
<langsyntaxhighlight lang="rexx">/*REXX program displays permutations of N number of objects (1, 2, 3, ···). */
parse arg N y seed . /*obtain optional arguments from the CL*/
if N=='' | N=="," then N= 4 /*Not specified? Then use the default.*/
Line 1,996 ⟶ 2,167:
end /*p*/
parse value @.p @.q with @.q @.p
return 1</langsyntaxhighlight>
{{out|output|text=&nbsp; when using the default inputs:}}
<pre>
Line 2,028 ⟶ 2,199:
 
=={{header|Ring}}==
<langsyntaxhighlight lang="ring">
# Project : Permutations/Rank of a permutation
 
Line 2,070 ⟶ 2,241:
last = last - 1
end
</syntaxhighlight>
</lang>
Output:
<pre>
Line 2,100 ⟶ 2,271:
 
=={{header|Ruby}}==
<langsyntaxhighlight lang="ruby">class Permutation
include Enumerable
attr_reader :num_elements, :size
Line 2,137 ⟶ 2,308:
n.zero? ? 1 : n.downto(1).inject(:*)
end
end</langsyntaxhighlight>
Demo:
<langsyntaxhighlight lang="ruby">puts "All permutations of 3 items from and back to rank."
perm = Permutation.new(3)
(0...perm.size).each{|num| puts "#{num} --> #{prm=perm.unrank(num)} --> #{perm.rank(prm)}"}
Line 2,158 ⟶ 2,329:
p prm = perm.unrank(r)
p perm.rank(prm) == r
end</langsyntaxhighlight>
{{out}}
<pre style="overflow:auto">
Line 2,192 ⟶ 2,363:
 
=={{header|Scala}}==
<langsyntaxhighlight lang="scala">import scala.math._
 
def factorial(n: Int): BigInt = {
Line 2,214 ⟶ 2,385:
case Nil => BigInt(0)
case x :: rest => factorial(rest.size) * rest.count(ord.lt(_, x)) + permutationToIndex(rest)
}</langsyntaxhighlight>
<langsyntaxhighlight lang="scala">def check(n: Int, x: BigInt): Boolean = {
val perm = indexToPermutation(n, x)
val xOut = permutationToIndex(perm)
Line 2,226 ⟶ 2,397:
} else {
println("Failed")
}</langsyntaxhighlight>
 
{{out}}
Line 2,240 ⟶ 2,411:
=={{header|Tcl}}==
{{trans|D}}
<langsyntaxhighlight lang="tcl"># A functional swap routine
proc swap {v idx1 idx2} {
lset v $idx2 [lindex $v $idx1][lset v $idx1 [lindex $v $idx2];subst ""]
Line 2,273 ⟶ 2,444:
}}
return [apply $mrRank1 $mrRank1 [llength $vec] $vec $inv]
}</langsyntaxhighlight>
Demonstrating:
<langsyntaxhighlight lang="tcl">proc factorial {n} {
for {set result 1; set i 2} {$i <= $n} {incr i} {
set result [expr {$result * $i}]
Line 2,298 ⟶ 2,469:
puts [format "%20lld: \[%s\] = %lld" \
$rank [join $items2 ", "] [computeRank $items2]]
}</langsyntaxhighlight>
{{out}}
<pre style="overflow:auto">
Line 2,332 ⟶ 2,503:
</pre>
The above code is not a particularly good use of a random number generator; the Tcl PRNG does not generate enough bits of true randomness per call to <code>rand()</code> for it to be useful in such a simplistic approach. However, it will do for the purposes of demonstration. A more sophisticated RNG is this one:
<langsyntaxhighlight lang="tcl">proc uniform {limit} {
set bits [expr {ceil(log($limit)/log(2))+10}]
for {set b [set r 0]} {$b < $bits} {incr b 16} {
Line 2,338 ⟶ 2,509:
}
return [expr {$r % $limit}]
}</langsyntaxhighlight>
===Addressing the extra credit===
The technique above can generate any random permutation of a list, but an equally viable approach (and one especially suitable to the SO question where the number of required permutations is small with respect to the number of possible permutations) would be to use a [[Knuth shuffle]] on a list and just use that with a quick check for repetitions, which could be implemented using a simple hashing check. (On the other hand, building a hash table of a million strings of 144 characters would not be too awkward on modern hardware.)
Line 2,345 ⟶ 2,516:
{{trans|Kotlin}}
{{libheader|Wren-fmt}}
<langsyntaxhighlight ecmascriptlang="wren">import "random" for Random
import "./fmt" for Fmt
 
var swap = Fn.new { |a, i, j|
Line 2,407 ⟶ 2,578:
getPermutation.call(r, 12, tv)
Fmt.print("$9d -> $n -> $d", r, tv, getRank.call(12, tv))
}</langsyntaxhighlight>
 
{{out}}
Sample output:
<pre>
0 -> [1, 2, 0] -> 0
Line 2,451 ⟶ 2,623:
=={{header|zkl}}==
{{trans|D}}
<langsyntaxhighlight lang="zkl">fcn computePermutation(items,rank){ // in place permutation of items
foreach n in ([items.len()..1,-1]){
r:=rank%n;
Line 2,458 ⟶ 2,630:
}
items
}</langsyntaxhighlight>
<langsyntaxhighlight lang="zkl"> /// Return the rank of a permutation.
fcn computeRank(perm){
N,p2,inv := perm.len(), perm.copy(), List.createLong(N,0);
Line 2,470 ⟶ 2,642:
s + n*self.fcn(i,p2,inv);
}(N,p2,inv);
}</langsyntaxhighlight>
<langsyntaxhighlight lang="zkl"> // do some random permutations of 4
fcn factorial(n){ (1).reduce(n,'*) }
items,max:=(4).toList(),factorial(items.len()); // (0,1,2,3), read only
Line 2,485 ⟶ 2,657:
p:=computePermutation(items.copy(),rank);
println("%12d: %s = %d".fmt(rank,p,computeRank(p)));
}</langsyntaxhighlight>
{{out}}
<pre>
Line 2,502 ⟶ 2,674:
computePermutation works fine with BigInts but there is no current way to generate a random number in range to 250!
If a 63 bit range was OK, then (but don't hold your breath, this takes a while):
<langsyntaxhighlight lang="zkl">var [const] BN=Import("zklBigNum"); // libGMP
one44Bang:=BN(144).factorial(); // 250 digits
// Needed: random number [0,one44Bang)
do(0d1_000_000){
p:=computePermutation((144).toList().copy(),(0).random((0).MAX));
}</langsyntaxhighlight>
and the TCL idea of shuffles (List.shuffle()) makes more sense.
PureFox
9,479

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/220715...351742"