Permutations/Rank of a permutation: Difference between revisions

Permutations/Rank of a permutation (view source)

Revision as of 12:48, 24 January 2024

33,529 bytes added , 4 months ago

m

→‎{{header|Wren}}: Minor tidy

PureFox

9,479

edits

Revision as of 07:54, 29 October 2017 (view source) CalmoSoft (talk \| contribs) (→‎{{header\|Ring}}) ← Older edit		Revision as of 12:48, 24 January 2024 (view source) PureFox (talk \| contribs) m (→‎{{header\|Wren}}: Minor tidy) Newer edit →
(25 intermediate revisions by 15 users not shown)
Line 54: # [http://stackoverflow.com/a/1506337/10562 Another answer] on Stack Overflow to a different question that explains its algorithm in detail. <br><br> ;Related tasks: #[[Factorial_base_numbers_indexing_permutations_of_a_collection]] <br><br> =={{header\|11l}}== {{trans\|Nim}} <syntaxhighlight lang="11l">UInt32 seed = 0 F nonrandom() :seed = 1664525 * :seed + 1013904223 R (:seed >> 16) / Float(FF'FF) F mrUnrank1(&vec, rank, n) I n < 1 {R} V (q, r) = divmod(rank, n) swap(&vec[r], &vec[n - 1]) mrUnrank1(&vec, q, n - 1) F mrRank1(&vec, &inv, n) I n < 2 {R 0} V s = vec[n - 1] swap(&vec[n - 1], &vec[inv[n - 1]]) swap(&inv[s], &inv[n - 1]) R s + n * mrRank1(&vec, &inv, n - 1) F getPermutation(&vec, rank) L(i) 0 .< vec.len {vec[i] = i} mrUnrank1(&vec, rank, vec.len) F getRank(vec) V v = [0] * vec.len V inv = [0] * vec.len L(val) vec v[L.index] = val inv[val] = L.index R mrRank1(&v, &inv, vec.len) V tv3 = [0] * 3 L(r) 6 getPermutation(&tv3, r) print(‘#2 -> #. -> #.’.format(r, tv3, getRank(tv3))) print() V tv4 = [0] * 4 L(r) 24 getPermutation(&tv4, r) print(‘#2 -> #. -> #.’.format(r, tv4, getRank(tv4))) print() V tv12 = [0] * 12 L 4 V r = Int(nonrandom() * factorial(12)) getPermutation(&tv12, r) print(‘#9 -> #. -> #.’.format(r, tv12, getRank(tv12)))</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 0 -> [1, 2, 3, 0] -> 0 1 -> [3, 2, 0, 1] -> 1 2 -> [1, 3, 0, 2] -> 2 3 -> [1, 2, 0, 3] -> 3 4 -> [2, 3, 1, 0] -> 4 5 -> [2, 0, 3, 1] -> 5 6 -> [3, 0, 1, 2] -> 6 7 -> [2, 0, 1, 3] -> 7 8 -> [1, 3, 2, 0] -> 8 9 -> [3, 0, 2, 1] -> 9 10 -> [1, 0, 3, 2] -> 10 11 -> [1, 0, 2, 3] -> 11 12 -> [2, 1, 3, 0] -> 12 13 -> [2, 3, 0, 1] -> 13 14 -> [3, 1, 0, 2] -> 14 15 -> [2, 1, 0, 3] -> 15 16 -> [3, 2, 1, 0] -> 16 17 -> [0, 2, 3, 1] -> 17 18 -> [0, 3, 1, 2] -> 18 19 -> [0, 2, 1, 3] -> 19 20 -> [3, 1, 2, 0] -> 20 21 -> [0, 3, 2, 1] -> 21 22 -> [0, 1, 3, 2] -> 22 23 -> [0, 1, 2, 3] -> 23 113071713 -> [2, 0, 4, 8, 10, 1, 6, 5, 7, 3, 11, 9] -> 113071713 133434854 -> [4, 9, 10, 5, 6, 11, 3, 7, 8, 0, 1, 2] -> 133434854 392556922 -> [9, 5, 1, 8, 7, 2, 11, 3, 4, 6, 0, 10] -> 392556922 319911818 -> [3, 11, 1, 9, 8, 7, 6, 0, 5, 10, 4, 2] -> 319911818 </pre> =={{header\|C}}== === C: Myrvold and Ruskey === This is algorithm #1 from the M&R paper. <~~lang~~syntaxhighlight lang="c">#include <stdio.h> #include <stdlib.h> Line 126 ⟶ 219: } } </syntaxhighlight> ~~</lang>~~ {{out}} Line 153 ⟶ 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 158 ⟶ 353: {{trans\|C}} Currently this doesn't use BigInts. <~~lang~~syntaxhighlight lang="d">import std.stdio, std.algorithm, std.range; alias TRank = ulong; Line 220 ⟶ 415: writefln("%20d: %s = %d", rank, items2, items2.computeRank); } }</~~lang~~syntaxhighlight> {{out}} <pre> 0: [1, 2, 3, 0] = 0 Line 252 ⟶ 447: 6844249986266452118: [18, 20, 11, 19, 10, 12, 8, 9, 3, 13, 7, 15, 0, 1, 6, 5, 14, 17, 4, 16, 2] = 6844249986266452118 12804085840772788456: [8, 4, 14, 2, 5, 12, 19, 0, 9, 17, 11, 7, 16, 1, 20, 6, 10, 15, 18, 3, 13] = 12804085840772788456</pre> =={{header\|FreeBASIC}}== ===Up to 20 objects=== <~~lang~~syntaxhighlight lang="freebasic">' version 31-03-2017 ' compile with: fbc -s console Line 403 ⟶ 599: Print : Print "hit any key to end program" Sleep End</~~lang~~syntaxhighlight> {{out}} <pre>Rank: unrank1 rank1 Line 438 ⟶ 634: ===Using GMP for the big numbers=== {{libheader\|GMP}} <~~lang~~syntaxhighlight lang="freebasic">' version 31-03-2017 ' compile with: fbc -s console Line 554 ⟶ 750: Print : Print "hit any key to end program" Sleep End</~~lang~~syntaxhighlight> {{out}} <pre>862993243747395020367391904490190117106585269146708404403331561502140758428008657463653366643611155380240799622282374456087743515643868809722278635878978733132591027133490410275442362000562723356064257191755491520940533177124123076535632269113257248 Line 575 ⟶ 771: =={{header\|Go}}== <~~lang~~syntaxhighlight lang="go">package main import ( Line 656 ⟶ 852: fmt.Println(r, MRPerm(r, n)) } }</~~lang~~syntaxhighlight> {{out}} <pre> Line 675 ⟶ 871: =={{header\|Haskell}}== Without the random part. <syntaxhighlight lang ="haskell">fact n:: =Int ~~foldr () 1~~-> ~~[1..n]~~Int fact n = product [1 .. n] -- Always assume elements are unique. ~~-- always assume elements are unique~~ rankPerm [] _ = [] rankPerm list n = c : rankPerm (a ++ b) r ~~where~~ where ~~(q,r) = n `divMod` fact (length list - 1)~~ (aq,~~c:b~~ r) = ~~splitAt~~n q`divMod` fact (length list - 1) (a, c:b) = splitAt q list permRank [] = 0 permRank (x:xs) = length (filter (< x) xs) fact (length xs) + permRank xs main =:: ~~mapM_~~IO ~~f [0..23] where~~() main = mapM_ f [0 .. 23] ~~f n = print (n, p, permRank p) where~~ where ~~p = rankPerm [0..3] n</lang>~~ f n = print (n, p, permRank p) where p = rankPerm [0 .. 3] n</syntaxhighlight> {{out}} from rank to permutation back to rank: Line 721 ⟶ 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. <~~lang~~syntaxhighlight lang="j"> A. 2 0 1 NB. return rank of permutation 4 4 A. i.3 NB. return permutation of rank 4 Line 745 ⟶ 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...</~~lang~~syntaxhighlight> =={{header\|Java}}== Line 755 ⟶ 957: '''Code:''' <~~lang~~syntaxhighlight lang="java">import java.math.BigInteger; import java.util.; Line 826 ⟶ 1,028: } }</~~lang~~syntaxhighlight> {{out}} Line 847 ⟶ 1,049: 3867119554188057320189830921237689379982446172130048814726708614069209339326961586538911571940960420075292018388619717817588596221122134526830668232334295443338743434633976186486468178683660450737612737202079329785249513121919049677640145391966805396 --> [100, 47, 42, 69, 16, 43, 66, 107, 73, 79, 12, 80, 41, 50, 9, 126, 95, 36, 26, 51, 123, 45, 52, 3, 93, 29, 83, 17, 82, 5, 81, 85, 131, 122, 113, 6, 75, 28, 59, 64, 138, 20, 74, 114, 27, 65, 105, 116, 62, 142, 141, 35, 115, 4, 49, 78, 2, 97, 130, 89, 110, 57, 90, 127, 72, 119, 44, 13, 99, 112, 118, 103, 77, 125, 92, 133, 104, 60, 76, 70, 23, 53, 55, 38, 108, 84, 96, 54, 128, 140, 25, 11, 24, 7, 124, 136, 8, 111, 46, 63, 31, 1, 102, 67, 94, 0, 132, 37, 91, 10, 101, 22, 34, 68, 14, 71, 21, 87, 30, 40, 129, 120, 18, 58, 61, 86, 56, 143, 32, 33, 15, 88, 137, 98, 106, 109, 135, 134, 48, 139, 121, 39, 19, 117] --> 3867119554188057320189830921237689379982446172130048814726708614069209339326961586538911571940960420075292018388619717817588596221122134526830668232334295443338743434633976186486468178683660450737612737202079329785249513121919049677640145391966805396 4939977610738364532346788397924709243352263476618646232552639571823537393872611379891069437022354024663565745556550101222893478863124970842071831822047445469519025638779057663111504542116305321498448757808078281473228131641155000612722388784688217279 --> [128, 23, 97, 115, 131, 15, 21, 61, 90, 116, 32, 80, 59, 137, 7, 63, 43, 55, 11, 83, 27, 138, 114, 40, 122, 4, 132, 125, 54, 25, 95, 111, 72, 84, 17, 13, 31, 10, 16, 52, 126, 129, 91, 18, 47, 53, 34, 119, 57, 41, 110, 134, 108, 58, 127, 82, 66, 70, 33, 9, 98, 142, 100, 121, 30, 105, 36, 120, 48, 2, 28, 37, 5, 46, 44, 71, 107, 45, 19, 141, 86, 76, 109, 143, 118, 3, 130, 89, 73, 42, 56, 94, 35, 67, 136, 12, 74, 123, 24, 64, 93, 26, 14, 112, 88, 29, 77, 60, 85, 6, 0, 96, 103, 62, 50, 124, 8, 135, 22, 79, 68, 139, 78, 101, 20, 117, 51, 133, 81, 102, 39, 99, 113, 38, 104, 69, 106, 75, 92, 87, 49, 1, 140, 65] --> 4939977610738364532346788397924709243352263476618646232552639571823537393872611379891069437022354024663565745556550101222893478863124970842071831822047445469519025638779057663111504542116305321498448757808078281473228131641155000612722388784688217279</pre> =={{header\|jq}}== '''Adapted from [[#Wren\|Wren]]''' {{works with\|jq}} '''Works with gojq, the Go implementation of jq''' '''Preliminaries''' <syntaxhighlight 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. def divmod($j): . as $i \| ($i % $j) as $mod \| [($i - $mod) / $j, $mod] ; # Input may be an object or an array def swap($i; $j): .[$i] as $t \| .[$i] = .[$j] \| .[$j] = $t; def factorial: . as $n \| reduce range(2; $n) as $i ($n; . $i); def lpad($len): tostring \| ($len - length) as $l \| (" " * $l)[:$l] + .;</syntaxhighlight> '''The Tasks''' <syntaxhighlight lang="jq"># Myrvold and Ruskey algorithm # The input should be a permutation of 0 ... $n-1 inclusive def mrUnrank1($rank; $n): if $n < 1 then . else ($rank\|divmod($n)) as [$q, $r] \| swap($r; $n - 1) \| mrUnrank1($q; $n - 1) end ; # The input should be a permutation of 0 ... $n-1 inclusive def mrRank1($n; $vec): if $n < 2 then 0 else . as $inv \| $vec \| .[$n-1] as $s \| swap($n - 1; $inv[$n-1]) as $vec \| $inv \| swap($s; $n - 1) \| $s + $n * mrRank1($n - 1; $vec) end; def getPermutation($rank; $n): [range(0; $n)] \| mrUnrank1($rank; $n) ; def getRank($n; $vec): reduce range(0; $n) as $i ( null; .[$vec[$i]] = $i ) \| mrRank1($n; $vec); def task($k): "\($k)!", (range(0; $k\|factorial) as $r \| getPermutation($r; $k) \| [ ($r\|lpad(2)), tostring, (getRank($k; .) \| lpad(2)) ] \| join(" -> ") ); def task3: def randoms: 43154690, 150112966, 15732396, 157551691; "\("#"\|lpad(10)) -> \("permutation"\|lpad(27)) -> \("rank"\|lpad(10))", (randoms as $r \| getPermutation($r; 12) \| "\($r\|lpad(10)) -> \(lpad(27)) -> \(getRank(12;.)\|lpad(10))" ); task(3), "", task(4), "", task3</syntaxhighlight> {{out}} <pre> 3! 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 4! 0 -> [1,2,3,0] -> 0 1 -> [3,2,0,1] -> 1 2 -> [1,3,0,2] -> 2 3 -> [1,2,0,3] -> 3 4 -> [2,3,1,0] -> 4 5 -> [2,0,3,1] -> 5 6 -> [3,0,1,2] -> 6 7 -> [2,0,1,3] -> 7 8 -> [1,3,2,0] -> 8 9 -> [3,0,2,1] -> 9 10 -> [1,0,3,2] -> 10 11 -> [1,0,2,3] -> 11 12 -> [2,1,3,0] -> 12 13 -> [2,3,0,1] -> 13 14 -> [3,1,0,2] -> 14 15 -> [2,1,0,3] -> 15 16 -> [3,2,1,0] -> 16 17 -> [0,2,3,1] -> 17 18 -> [0,3,1,2] -> 18 19 -> [0,2,1,3] -> 19 20 -> [3,1,2,0] -> 20 21 -> [0,3,2,1] -> 21 22 -> [0,1,3,2] -> 22 23 -> [0,1,2,3] -> 23 # -> permutation -> rank 43154690 -> [1,3,10,11,7,8,6,0,4,9,5,2] -> 43154690 150112966 -> [8,0,1,5,2,7,11,3,6,9,4,10] -> 150112966 15732396 -> [1,8,6,11,3,5,7,10,2,4,9,0] -> 15732396 157551691 -> [6,0,1,9,10,2,11,5,8,3,4,7] -> 157551691 </pre> =={{header\|Julia}}== Line 854 ⟶ 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. <syntaxhighlight lang="julia">using Printf ~~<lang Julia>~~ nobjs = 4 a = collect(1:nobjs) Line 880 ⟶ 1,207: println(" ", p, " (", prank, ")") end </syntaxhighlight> ~~</lang>~~ {{out}} Line 919 ⟶ 1,246: =={{header\|Kotlin}}== {{trans\|C}} <~~lang~~syntaxhighlight lang="scala">// version 1.1.2 import java.util.Random Line 983 ⟶ 1,310: System.out.printf("%9d -> %s -> %d\n", r, tv.contentToString(), getRank(12, tv)) } }</~~lang~~syntaxhighlight> {{out}} Line 1,025 ⟶ 1,352: </pre> =={{header\|Mathematica}}/{{header\|Wolfram Language}}== {{trans\|Haskell}} <~~lang~~syntaxhighlight lang="mathematica">fromrank[list_, 0] := list; fromrank[list_, n_] := Prepend[fromrank[DeleteCases[list, #], Line 1,040 ⟶ 1,367: Do[Print@fromrank[Range[0, 12 - 1], RandomInteger[12!]], {4}]; Do[Print@fromrank[Range[0, 144 - 1], RandomInteger[144!]], {4}];</~~lang~~syntaxhighlight> {{Out}} <pre>{0,{0,1,2,3},0} Line 1,074 ⟶ 1,401: {118,52,6,67,24,8,105,3,55,29,99,111,14,21,0,48,45,80,131,63,76,16,68,25,125,72,47,98,126,75,28,30,85,143,129,90,32,54,119,117,116,88,115,73,123,11,7,78,141,87,114,91,96,37,106,46,31,133,100,20,17,27,42,36,134,138,120,9,66,74,112,33,77,101,104,12,64,121,40,58,43,136,61,135,132,79,81,49,69,19,82,4,53,1,38,84,108,56,70,86,10,89,107,44,15,35,26,5,110,137,62,140,92,113,103,142,97,51,93,65,128,18,95,50,102,23,2,57,13,34,71,130,83,94,39,60,59,109,122,41,127,22,124,139} {100,48,125,13,85,95,54,128,111,79,10,103,83,52,143,78,16,114,133,105,43,53,104,37,12,5,17,26,68,61,73,141,34,14,138,140,59,21,77,99,29,117,108,62,39,41,45,91,116,25,131,31,118,94,90,46,49,98,51,137,7,101,44,56,50,87,110,120,142,27,135,18,58,113,69,75,42,107,130,86,80,127,123,15,3,1,122,47,134,106,119,92,136,20,55,74,36,65,67,72,81,0,23,96,32,88,126,97,19,64,4,102,76,66,35,132,139,60,129,6,30,124,57,70,71,82,22,112,24,9,115,63,8,33,89,93,84,38,28,11,109,121,2,40}</pre> =={{header\|Nim}}== {{trans\|Kotlin}} <syntaxhighlight lang="nim">func mrUnrank1(vec: var openArray[int]; rank, n: int) = if n < 1: return let q = rank div n let r = rank mod n swap vec[r], vec[n - 1] vec.mrUnrank1(q, n - 1) func mrRank1(vec, inv: var openArray[int]; n: int): int = if n < 2: return 0 let s = vec[n - 1] swap vec[n - 1], vec[inv[n - 1]] swap inv[s], inv[n - 1] result = s + n * vec.mrRank1(inv, n - 1) func getPermutation(vec: var openArray[int]; rank: int) = for i in 0..vec.high: vec[i] = i vec.mrUnrank1(rank, vec.len) func getRank(vec: openArray[int]): int = var v, inv = newSeq[int](vec.len) for i, val in vec: v[i] = val inv[val] = i result = v.mrRank1(inv, vec.len) when isMainModule: import math, random, sequtils, strformat randomize() var tv3: array[3, int] for r in 0..5: tv3.getPermutation(r) echo &"{r:>2} → {tv3} → {tv3.getRank()}" echo "" var tv4: array[4, int] for r in 0..23: tv4.getPermutation(r) echo &"{r:>2} → {tv4} → {tv4.getRank()}" echo "" var tv12: array[12, int] for r in newSeqWith(4, rand(fac(12))): tv12.getPermutation(r) echo &"{r:>9} → {tv12} → {tv12.getRank()}"</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 0 → [1, 2, 3, 0] → 0 1 → [3, 2, 0, 1] → 1 2 → [1, 3, 0, 2] → 2 3 → [1, 2, 0, 3] → 3 4 → [2, 3, 1, 0] → 4 5 → [2, 0, 3, 1] → 5 6 → [3, 0, 1, 2] → 6 7 → [2, 0, 1, 3] → 7 8 → [1, 3, 2, 0] → 8 9 → [3, 0, 2, 1] → 9 10 → [1, 0, 3, 2] → 10 11 → [1, 0, 2, 3] → 11 12 → [2, 1, 3, 0] → 12 13 → [2, 3, 0, 1] → 13 14 → [3, 1, 0, 2] → 14 15 → [2, 1, 0, 3] → 15 16 → [3, 2, 1, 0] → 16 17 → [0, 2, 3, 1] → 17 18 → [0, 3, 1, 2] → 18 19 → [0, 2, 1, 3] → 19 20 → [3, 1, 2, 0] → 20 21 → [0, 3, 2, 1] → 21 22 → [0, 1, 3, 2] → 22 23 → [0, 1, 2, 3] → 23 432161730 → [0, 11, 8, 10, 3, 7, 4, 1, 9, 2, 5, 6] → 432161730 107135296 → [7, 6, 3, 11, 8, 5, 10, 2, 9, 1, 0, 4] → 107135296 242872115 → [10, 1, 8, 4, 6, 5, 9, 3, 7, 0, 2, 11] → 242872115 196796546 → [8, 0, 9, 6, 4, 1, 7, 5, 3, 11, 10, 2] → 196796546</pre> =={{header\|PARI/GP}}== The functions are built into GP already: <code>numtoperm</code> and <code>permtonum</code> <~~lang~~syntaxhighlight 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!)))</~~lang~~syntaxhighlight> {{out}} <pre>%1 = 1 Line 1,086 ⟶ 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}} <~~lang~~syntaxhighlight lang="perl">use ntheory qw/:all/; my $n = 3; Line 1,106 ⟶ 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,137 ⟶ 1,554: </pre> =={{header\|~~Perl 6~~Phix}}== {{trans\|C}} ~~It is similar to Haskell, but separate something like [https://en.wikipedia.org/wiki/Inversion_(discrete_mathematics) inversion vector].~~ <!--<syntaxhighlight lang="phix">(phixonline)--> ~~It is easy generate random inversion vector without BigInt.~~ <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> ~~<lang perl6>use v6;~~ <span style="color: #004080;">integer</span> <span style="color: #000000;">r</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</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;">inv</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: #000000;">r</span><span style="color: #0000FF;">)</span> ~~sub rank2inv ( $rank, $n = * ) {~~ <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: #000000;">r</span> <span style="color: #008080;">do</span> ~~$rank.polymod( 1 ..^ $n );~~ <span style="color: #000000;">inv</span><span style="color: #0000FF;">[</span><span style="color: #000000;">l</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> } <span style="color: #008080;">end</span> <span style="color: #008080;">for</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">mul</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span> ~~sub inv2rank ( @inv ) {~~ <span style="color: #000000;">l</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">l</span><span style="color: #0000FF;">)</span> [+] @inv Z* [\] 1, 1, + 1 ... * <span style="color: #008080;">for</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">=</span><span style="color: #000000;">r</span> <span style="color: #008080;">to</span> <span style="color: #000000;">2</span> <span style="color: #008080;">by</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span> } <span style="color: #004080;">integer</span> <span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">l</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: #000000;">inv</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n</span><span style="color: #0000FF;">]+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">s</span> ~~sub inv2perm ( @inv, @items is copy = ^@inv.elems ) {~~ <span style="color: #000000;">inv</span><span style="color: #0000FF;">[</span><span style="color: #000000;">s</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">inv</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n</span><span style="color: #0000FF;">]</span> ~~my @perm;~~ <span style="color: #000000;">res</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">s</span><span style="color: #0000FF;"></span><span style="color: #000000;">mul</span> ~~for @inv.reverse -> $i {~~ <span style="color: #000000;">mul</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">n</span> ~~@perm.append: @items.splice: $i, 1;~~ <span style="color: #008080;">end</span> <span style="color: #008080;">for</span> } <span style="color: #008080;">return</span> <span style="color: #000000;">res</span> ~~@perm;~~ <span style="color: #008080;">end</span> <span style="color: #008080;">function</span> } <span style="color: #7060A8;">puts</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"rank->permute->rank:\n"</span><span style="color: #0000FF;">)</span> ~~sub perm2inv ( @perm ) { #not in linear time~~ <span style="color: #004080;">sequence</span> <span style="color: #000000;">l</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">tagset</span><span style="color: #0000FF;">(</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">)</span> ( <span style="color: #008080;">for</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">factorial</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">l</span><span style="color: #0000FF;">))</span> <span style="color: #008080;">do</span> ~~{ @perm[++$ .. ].grep( < $^cur ).elems } for @perm;~~ <span style="color: #004080;">sequence</span> <span style="color: #000000;">p</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">permute</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> ~~).reverse;~~ <span style="color: #0000FF;">?{</span><span style="color: #000000;">n</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p</span><span style="color: #0000FF;">,</span><span style="color: #000000;">get_rank</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p</span><span style="color: #0000FF;">)}</span> } <span style="color: #008080;">end</span> <span style="color: #008080;">for</span> ~~for~~ ^6 { <span style="color: #7060A8;">puts</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"4 random individual samples of 12 items:\n"</span><span style="color: #0000FF;">)</span> ~~my @row.push: $^rank;~~ <span style="color: #000000;">l</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">tagset</span><span style="color: #0000FF;">(</span><span style="color: #000000;">11</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">)</span> ~~for ( .&rank2inv(3) , &inv2perm, &perm2inv, &inv2rank ) -> &code {~~ <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: #000000;">4</span> <span style="color: #008080;">do</span> ~~@row.push: code( @row[-1] );~~ <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> ~~say @row;~~ <!--</syntaxhighlight>--> } ~~my $perms = 4; #100;~~ ~~my $n = 12; #144;~~ ~~say 'Via BigInt rank';~~ ~~for ( ( ^([] 1 .. $n) ).pick($perms) ) {~~ ~~say $^rank.&rank2inv($n).&inv2perm;~~ }; ~~say 'Via inversion vectors';~~ ~~for ( { my $i=0; inv2perm (^++$i).roll xx $n } ... ).unique( with => &[eqv] ).[^$perms] {~~ ~~.say;~~ }; ~~say 'Via Perl 6 method pick';~~ ~~for ( { [(^$n).pick()] } ... ).unique( with => &[eqv] ).head($perms) {~~ ~~.say~~ }; ~~</lang>~~ {{out}} <pre> rank->permute->rank: ~~[0 (0 0 0) [0 1 2] (0 0 0) 0]~~ {0,{1,2,0},0} ~~[1 (0 1 0) [0 2 1] (0 1 0) 1]~~ {1,{2,0,1},1} ~~[2 (0 0 1) [1 0 2] (0 0 1) 2]~~ {2,{1,0,2},2} ~~[3 (0 1 1) [1 2 0] (0 1 1) 3]~~ {3,{2,1,0},3} ~~[4 (0 0 2) [2 0 1] (0 0 2) 4]~~ {4,{0,2,1},4} ~~[5 (0 1 2) [2 1 0] (0 1 2) 5]~~ {5,{0,1,2},5} ~~Via BigInt rank~~ 4 random individual samples of 12 items: ~~[4 3 1 8 6 2 0 7 9 11 5 10]~~ {4,2,10,9,0,1,5,6,7,3,8,11} ~~[0 8 11 4 9 3 7 5 2 6 10 1]~~ {4,7,9,2,8,11,1,3,10,6,0,5} ~~[5 7 9 11 10 6 4 1 2 3 0 8]~~ {7,9,1,3,2,11,5,6,8,4,10,0} ~~[9 11 8 6 3 5 7 2 4 0 1 10]~~ {4,0,9,7,8,11,5,6,10,3,1,2} ~~Via inversion vectors~~ ~~[9 0 3 1 8 2 4 5 11 7 10 6]~~ ~~[7 3 1 10 0 6 4 11 2 9 8 5]~~ ~~[9 8 5 11 1 10 0 7 4 6 2 3]~~ ~~[10 8 6 5 4 9 0 2 11 7 1 3]~~ ~~Via Perl 6 method pick~~ ~~[11 0 7 10 9 4 1 8 6 5 2 3]~~ ~~[4 5 8 3 2 1 7 9 11 0 10 6]~~ ~~[11 7 9 4 0 8 10 1 5 2 6 3]~~ ~~[11 10 0 3 4 6 7 9 8 5 1 2]~~ </pre> It is worth noting that while the permute builtin can scramble anything, the get_rank function above<br> (like most others on this page) can only handle permulations of the integers 0 to n-1. Of course should<br> you permute indexes rather than the (non-integer) data, that does not matter anyway. It proved utterly trivial to convert that to bigatoms, however also utterly pointless, since it would take<br> over 5 days to generate a million perms, whereas a million shuffle(l) (of 144 items) takes just 20 seconds,<br> and in fact storing the integer(string) ranks takes twice as much space as 144 small integers anyway. =={{header\|Python}}== Line 1,221 ⟶ 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). <~~lang~~syntaxhighlight lang="python">from math import factorial as fact from random import randrange from textwrap import wrap Line 1,306 ⟶ 1,702: test1('First ordering:', unranker1, ranker1) test1('Second ordering:', unranker2, ranker2) test2('First ordering, large number of perms:', unranker1)</~~lang~~syntaxhighlight> {{out}} Line 1,376 ⟶ 1,772: 52, 15, 19, 46, 96, 45, 10, 54, 105, 143, 87, 119]</pre> ===Python: ~~Iterative~~Trotter-Johnson=== This uses the Trotter-Johnson permutations generator in which successive permutations differ by only one swap between two items.<br> ~~Functions ranker1 and ranker2 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:~~ Permutations with small differences in rank are likely to be "similar" in appearance (if rank difference << perm length). ~~<lang python>def ranker1(n, pi, pi1):~~ <syntaxhighlight lang="python">from random import randrange from typing import List Perm = List[int] _fact = [1] # factorials cache def print_perm(T: Perm) -> None: print(T) def tj_unrank(n: int, r: int) -> Perm: "Returns the r-ranked Trotter-Johnson permutation of integers 0..n-1" global _fact for i in range(len(_fact), n+2): # Extend factorial cache if necessary. _fact.append(_fact[i - 1] * i) pi: Perm = [0] * (n+2) pi[1] = 1 r2 = 0 for j in range(2, n+1): r1 = (r * _fact[j]) // _fact[n] k = r1 - jr2 if ((r2 % 2) == 0): for i in range(j-1, j - k - 1, -1): pi[i+1] = pi[i] pi[j-k] = j else: for i in range(j - 1, k, -1): pi[i+1] = pi[i] pi[k + 1] = j r2 = r1 return [i - 1 for i in pi[1:-1]] def tj_rank(p: Perm) -> int: "Returns the ranking of the Trotter-Johnson permutation p, of integers 0..n-1" n = len(p) assert set(p) == set(range(n)), f"Perm {p} not a perm of 0..{n-1}." pi = [0] + [i+1 for i in p] + [0] r = 0 for j in range(2, n + 1): i = k = 1 while pi[i] != j: if (pi[i] < j): k += 1 i += 1 if ((r % 2) == 0 ): r = jr+j-k else: r = jr+k-1 return r def tj_parity(p: Perm) -> int: "Returns the 0/1 parity of the Trotter-Johnson permutation p, of integers 0..n-1" n = len(p) assert set(p) == set(range(n)), f"Perm {p} not a perm of 0..{n-1}." pi = [0] + [i+1 for i in p] + [0] a, c = [0] (n + 1), 0 for j in range(1, n+1): if a[j] == 0: c += 1 a[j] = 1 i = j while ( pi[i] != j ): i = pi[i] a[i] = 1 return (n-c) % 2 def get_random_ranks(permsize, samplesize, fact): perms = fact[permsize] ranks = set() while len(ranks) < samplesize: ranks \|= set( randrange(perms) for r in range(samplesize - len(ranks)) ) return ranks if __name__ == '__main__': n = 3 print(f"Testing rank/unrank n={n}.\n"); for i in range(len(_fact), n+2): # Extend factorial cache if necessary. _fact.append(_fact[i - 1] * i) for r in range(_fact[n]): p = tj_unrank(n, r) rank = tj_rank(p) parity = tj_parity(p) print(f" Rank: {r:4} to perm: {p}, parity: {parity} back to rank: {rank}") for samplesize, n2 in [(4, 12), (3, 144)]: print('\n %i random individual samples of %i items:' % (samplesize, n2)) for i in range(len(_fact), max([n, n2])+2): # Extend factorial cache if necessary. _fact.append(_fact[i - 1] * i) for r in get_random_ranks(n2, samplesize, _fact): p = tj_unrank(n2, r) rank = tj_rank(p) parity = tj_parity(p) print(f" Rank: {r:10} to perm: {p}, parity: {parity} to rank: {rank:10}")</syntaxhighlight> {{out}} <pre>Testing rank/unrank n=3. Rank: 0 to perm: [0, 1, 2], parity: 0 back to rank: 0 Rank: 1 to perm: [0, 2, 1], parity: 1 back to rank: 1 Rank: 2 to perm: [2, 0, 1], parity: 0 back to rank: 2 Rank: 3 to perm: [2, 1, 0], parity: 1 back to rank: 3 Rank: 4 to perm: [1, 2, 0], parity: 0 back to rank: 4 Rank: 5 to perm: [1, 0, 2], parity: 1 back to rank: 5 4 random individual samples of 12 items: Rank: 224379355 to perm: [7, 8, 3, 6, 4, 2, 10, 11, 9, 0, 5, 1], parity: 1 to rank: 224379355 Rank: 23097790 to perm: [7, 4, 10, 6, 0, 1, 3, 9, 8, 5, 11, 2], parity: 0 to rank: 23097790 Rank: 117958174 to perm: [0, 8, 7, 3, 6, 10, 2, 5, 9, 1, 11, 4], parity: 0 to rank: 117958174 Rank: 346706871 to perm: [5, 6, 10, 11, 9, 1, 4, 2, 3, 0, 7, 8], parity: 1 to rank: 346706871 3 random individual samples of 144 items: 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</pre> ===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: <syntaxhighlight lang="python">def ranker1(n, pi, pi1): if n == 1: return 0 Line 1,394 ⟶ 1,921: pi1[s], pi1[i] = pi1[i], pi1[s] result += s * fact(i) return result</~~lang~~syntaxhighlight> =={{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. <~~lang~~syntaxhighlight lang="racket"> #lang racket (require math) (define-syntax def (make-rename-transformer #'match-define-values)) Line 1,414 ⟶ 2,009: (* (for/sum ([x xs] #:when (< x x0)) 1) (factorial (length xs))))])) </syntaxhighlight> ~~</lang>~~ {{out}} <pre> Line 1,445 ⟶ 2,040: (22 (3 2 0 1) 22) (23 (3 2 1 0) 23)) </pre> =={{header\|Raku}}== (formerly Perl 6) It is similar to Haskell, but separate something like [https://en.wikipedia.org/wiki/Inversion_(discrete_mathematics) inversion vector]. It is easy generate random inversion vector without BigInt. <syntaxhighlight lang="raku" line>use v6; sub rank2inv ( $rank, $n = * ) { $rank.polymod( 1 ..^ $n ); } sub inv2rank ( @inv ) { [+] @inv Z* [\] 1, 1, + 1 ... * } sub inv2perm ( @inv, @items is copy = ^@inv.elems ) { my @perm; for @inv.reverse -> $i { @perm.append: @items.splice: $i, 1; } @perm; } sub perm2inv ( @perm ) { #not in linear time ( { @perm[++$ .. ].grep( < $^cur ).elems } for @perm; ).reverse; } for ^6 { my @row.push: $^rank; for ( .&rank2inv(3) , &inv2perm, &perm2inv, &inv2rank ) -> &code { @row.push: code( @row[-1] ); } say @row; } my $perms = 4; #100; my $n = 12; #144; say 'Via BigInt rank'; for ( ( ^([] 1 .. $n) ).pick($perms) ) { say $^rank.&rank2inv($n).&inv2perm; }; say 'Via inversion vectors'; for ( { my $i=0; inv2perm (^++$i).roll xx $n } ... ).unique( with => &[eqv] ).[^$perms] { .say; }; say 'Via Raku method pick'; for ( { [(^$n).pick()] } ... ).unique( with => &[eqv] ).head($perms) { .say }; </syntaxhighlight> {{out}} <pre> [0 (0 0 0) [0 1 2] (0 0 0) 0] [1 (0 1 0) [0 2 1] (0 1 0) 1] [2 (0 0 1) [1 0 2] (0 0 1) 2] [3 (0 1 1) [1 2 0] (0 1 1) 3] [4 (0 0 2) [2 0 1] (0 0 2) 4] [5 (0 1 2) [2 1 0] (0 1 2) 5] Via BigInt rank [4 3 1 8 6 2 0 7 9 11 5 10] [0 8 11 4 9 3 7 5 2 6 10 1] [5 7 9 11 10 6 4 1 2 3 0 8] [9 11 8 6 3 5 7 2 4 0 1 10] Via inversion vectors [9 0 3 1 8 2 4 5 11 7 10 6] [7 3 1 10 0 6 4 11 2 9 8 5] [9 8 5 11 1 10 0 7 4 6 2 3] [10 8 6 5 4 9 0 2 11 7 1 3] Via Raku method pick [11 0 7 10 9 4 1 8 6 5 2 3] [4 5 8 3 2 1 7 9 11 0 10 6] [11 7 9 4 0 8 10 1 5 2 6 3] [11 10 0 3 4 6 7 9 8 5 1 2] </pre> Line 1,454 ⟶ 2,130: Since this REXX program generates permutations without recursive calls, testing for the limit for a   ''stack overflow''   wouldn't be necessary using this REXX program. <~~lang~~syntaxhighlight 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 4 /Not specified? Then use the default./ if y=='' \| y=="," then y=17 17 /* " " " " " " / if datatype(seed,'W') then call random ,,seed /can make RANDOM numbers repeatable. / permutes= permSets(N) /returns N! (number of permutations)./ w= length(permutes) /used for aligning the SAY output. / @.= do p=0 tofor permutes-1 /traipse through each of the permutes./ z= permSets(N, p) /get which of the permutation it is./ say 'for' N "items, permute rank" right(p,w) 'is: ' z @.p=z z /define a rank permutation in @ array./ end /p/ say / [↓] displays a particular perm rank/ say ' the permutation rank of' y "is: " @.y /display a particular ~~permuation~~permutation rank./ exit /stick a fork in it, we're all done. / /──────────────────────────────────────────────────────────────────────────────────────/ permSets: procedure expose @. #; #= 0; parse arg x,r,c; c= space(c); xm= x -1 do j=1 for x; @.j= j-1; end /j/ _=0; do u=2 for xm; _= _ @.u; end /u/ if r==# then return _; if c==_ then return # do while .permSets(x,0); #= #+1; _= @.1 do v=2 for xm; _= _ @.v; end /v/ if r==# then return _; if c==_ then return # end /while···/ return #+1 /──────────────────────────────────────────────────────────────────────────────────────/ .permSets: procedure expose @.; parse arg p,q; pm= p-1 do k=pm by -1 for pm; kp= k+1; if @.k<@.kp then do; q=k; leave; end end /k/ do j=q+1 while j<p; parse value @.j @.p with @.p @.j; p=p p-1 end /j/ if q==0 then return 0 do p=q+1 while @.p<@.q~~; end /p/~~ end /p/ parse value @.p @.q with @.q @.p return 1</~~lang~~syntaxhighlight> {{out\|output\|text=  when using the default inputs:}} <pre> Line 1,522 ⟶ 2,199: =={{header\|Ring}}== <~~lang~~syntaxhighlight lang="ring"> # Project : Permutations/Rank of a permutation ~~# Date : 2017/10/21~~ ~~# Author : Gal Zsolt (~ CalmoSoft ~)~~ ~~# Email : <calmosoft@gmail.com>~~ list = [0, 1, 2, 3] Line 1,567 ⟶ 2,241: last = last - 1 end </syntaxhighlight> ~~</lang>~~ Output: <pre> Line 1,597 ⟶ 2,271: =={{header\|Ruby}}== <~~lang~~syntaxhighlight lang="ruby">class Permutation include Enumerable attr_reader :num_elements, :size Line 1,634 ⟶ 2,308: n.zero? ? 1 : n.downto(1).inject(:) end end</~~lang~~syntaxhighlight> Demo: <~~lang~~syntaxhighlight 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 1,655 ⟶ 2,329: p prm = perm.unrank(r) p perm.rank(prm) == r end</~~lang~~syntaxhighlight> {{out}} <pre style="overflow:auto"> Line 1,687 ⟶ 2,361: </pre> Really generating one million unique random permutations of 144 elements would take an estimated 11 hours on one core of my machine. =={{header\|Scala}}== <syntaxhighlight lang="scala">import scala.math._ def factorial(n: Int): BigInt = { (1 to n).map(BigInt.apply).fold(BigInt(1))(_ * _) } def indexToPermutation(n: Int, x: BigInt): List[Int] = { indexToPermutation((0 until n).toList, x) } def indexToPermutation(ns: List[Int], x: BigInt): List[Int] = ns match { case Nil => Nil case _ => { val (iBig, xNew) = x /% factorial(ns.size - 1) val i = iBig.toInt ns(i) :: indexToPermutation(ns.take(i) ++ ns.drop(i + 1), xNew) } } def permutationToIndex[A](xs: List[A])(implicit ord: Ordering[A]): BigInt = xs match { case Nil => BigInt(0) case x :: rest => factorial(rest.size) * rest.count(ord.lt(_, x)) + permutationToIndex(rest) }</syntaxhighlight> <syntaxhighlight lang="scala">def check(n: Int, x: BigInt): Boolean = { val perm = indexToPermutation(n, x) val xOut = permutationToIndex(perm) println(s"$x -> $perm -> $xOut") xOut == x } if ((0 to 5).map(BigInt.apply).forall(check(3, _))) { println("Success!") } else { println("Failed") }</syntaxhighlight> {{out}} <pre>0 -> List(0, 1, 2) -> 0 1 -> List(0, 2, 1) -> 1 2 -> List(1, 0, 2) -> 2 3 -> List(1, 2, 0) -> 3 4 -> List(2, 0, 1) -> 4 5 -> List(2, 1, 0) -> 5 Success!</pre> =={{header\|Tcl}}== {{trans\|D}} <~~lang~~syntaxhighlight 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 1,723 ⟶ 2,444: }} return [apply $mrRank1 $mrRank1 [llength $vec] $vec $inv] }</~~lang~~syntaxhighlight> Demonstrating: <~~lang~~syntaxhighlight lang="tcl">proc factorial {n} { for {set result 1; set i 2} {$i <= $n} {incr i} { set result [expr {$result * $i}] Line 1,748 ⟶ 2,469: puts [format "%20lld: \[%s\] = %lld" \ $rank [join $items2 ", "] [computeRank $items2]] }</~~lang~~syntaxhighlight> {{out}} <pre style="overflow:auto"> Line 1,782 ⟶ 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: <~~lang~~syntaxhighlight 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 1,788 ⟶ 2,509: } return [expr {$r % $limit}] }</~~lang~~syntaxhighlight> ===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.) =={{header\|Wren}}== {{trans\|Kotlin}} {{libheader\|Wren-fmt}} <syntaxhighlight lang="wren">import "random" for Random import "./fmt" for Fmt var swap = Fn.new { \|a, i, j\| var t = a[i] a[i] = a[j] a[j] = t } var mrUnrank1 // recursive mrUnrank1 = Fn.new { \|rank, n, vec\| if (n < 1) return var q = (rank/n).floor var r = rank % n swap.call(vec, r, n - 1) mrUnrank1.call(q, n - 1, vec) } var mrRank1 // recursive mrRank1 = Fn.new { \|n, vec, inv\| if (n < 2) return 0 var s = vec[n-1] swap.call(vec, n - 1, inv[n-1]) swap.call(inv, s, n - 1) return s + n * mrRank1.call(n - 1, vec, inv) } var getPermutation = Fn.new { \|rank, n, vec\| for (i in 0...n) vec[i] = i mrUnrank1.call(rank, n, vec) } var getRank = Fn.new { \|n, vec\| var v = List.filled(n, 0) var inv = List.filled(n, 0) for (i in 0...n) { v[i] = vec[i] inv[vec[i]] = i } return mrRank1.call(n, v, inv) } var tv = List.filled(3, 0) for (r in 0..5) { getPermutation.call(r, 3, tv) Fmt.print("$2d -> $n -> $d", r, tv, getRank.call(3, tv)) } System.print() tv = List.filled(4, 0) for (r in 0..23) { getPermutation.call(r, 4, tv) Fmt.print("$2d -> $n -> $d", r, tv, getRank.call(4, tv)) } System.print() tv = List.filled(12, 0) var a = List.filled(4, 0) var rand = Random.new() var fact12 = (2..12).reduce(1) { \|acc, i\| acc * i } for (i in 0..3) a[i] = rand.int(fact12) for (r in a) { getPermutation.call(r, 12, tv) Fmt.print("$9d -> $n -> $d", r, tv, getRank.call(12, tv)) }</syntaxhighlight> {{out}} Sample output: <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 0 -> [1, 2, 3, 0] -> 0 1 -> [3, 2, 0, 1] -> 1 2 -> [1, 3, 0, 2] -> 2 3 -> [1, 2, 0, 3] -> 3 4 -> [2, 3, 1, 0] -> 4 5 -> [2, 0, 3, 1] -> 5 6 -> [3, 0, 1, 2] -> 6 7 -> [2, 0, 1, 3] -> 7 8 -> [1, 3, 2, 0] -> 8 9 -> [3, 0, 2, 1] -> 9 10 -> [1, 0, 3, 2] -> 10 11 -> [1, 0, 2, 3] -> 11 12 -> [2, 1, 3, 0] -> 12 13 -> [2, 3, 0, 1] -> 13 14 -> [3, 1, 0, 2] -> 14 15 -> [2, 1, 0, 3] -> 15 16 -> [3, 2, 1, 0] -> 16 17 -> [0, 2, 3, 1] -> 17 18 -> [0, 3, 1, 2] -> 18 19 -> [0, 2, 1, 3] -> 19 20 -> [3, 1, 2, 0] -> 20 21 -> [0, 3, 2, 1] -> 21 22 -> [0, 1, 3, 2] -> 22 23 -> [0, 1, 2, 3] -> 23 43154690 -> [1, 3, 10, 11, 7, 8, 6, 0, 4, 9, 5, 2] -> 43154690 150112966 -> [8, 0, 1, 5, 2, 7, 11, 3, 6, 9, 4, 10] -> 150112966 15732396 -> [1, 8, 6, 11, 3, 5, 7, 10, 2, 4, 9, 0] -> 15732396 157551691 -> [6, 0, 1, 9, 10, 2, 11, 5, 8, 3, 4, 7] -> 157551691 </pre> =={{header\|zkl}}== {{trans\|D}} <~~lang~~syntaxhighlight lang="zkl">fcn computePermutation(items,rank){ // in place permutation of items foreach n in ([items.len()..1,-1]){ r:=rank%n; Line 1,801 ⟶ 2,630: } items }</~~lang~~syntaxhighlight> <~~lang~~syntaxhighlight lang="zkl"> /// Return the rank of a permutation. fcn computeRank(perm){ N,p2,inv := perm.len(), perm.copy(), List.createLong(N,0); Line 1,813 ⟶ 2,642: s + nself.fcn(i,p2,inv); }(N,p2,inv); }</~~lang~~syntaxhighlight> <~~lang~~syntaxhighlight 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 1,828 ⟶ 2,657: p:=computePermutation(items.copy(),rank); println("%12d: %s = %d".fmt(rank,p,computeRank(p))); }</~~lang~~syntaxhighlight> {{out}} <pre> Line 1,845 ⟶ 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): <~~lang~~syntaxhighlight 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)); }</~~lang~~syntaxhighlight> and the TCL idea of shuffles (List.shuffle()) makes more sense.