Permutations/Rank of a permutation: Difference between revisions
Permutations/Rank of a permutation (view source)
Revision as of 07:21, 5 December 2021
, 2 years agoAdded 11l
Alextretyak (talk | contribs) (Added 11l) |
|||
Line 57:
#[[Factorial_base_numbers_indexing_permutations_of_a_collection]]
<br><br>
=={{header|11l}}==
{{trans|Nim}}
<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(i) 4
V r = Int(nonrandom() * factorial(12))
getPermutation(&tv12, r)
print(‘#9 -> #. -> #.’.format(r, tv12, getRank(tv12)))</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
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 ===
| |||