Anonymous user
Permutations/Rank of a permutation: Difference between revisions
→{{header|Nim}}
(Added Wren) |
|||
Line 1,082:
{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}}
<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()}"</lang>
{{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}}==
| |||