Permutations/Rank of a permutation: Difference between revisions
Permutations/Rank of a permutation (view source)
Revision as of 09:26, 1 December 2021
, 2 years ago→{{header|jq}}
Line 856:
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'''
<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] + .;</lang>
'''The Tasks'''
<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</lang>
{{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}}==
| |||