Permutations/Rank of a permutation: Difference between revisions
Added Kotlin
m (→Using GMP for the big numbes: typo) |
(Added Kotlin) |
||
Line 915:
[8,1,2,5,10,3,11,9,12,7,6,4] (279524016)
[1,10,4,12,6,5,8,9,3,2,7,11] (30095719)
</pre>
=={{header|Kotlin}}==
{{trans|C}}
<lang scala>// version 1.1.2
import java.util.Random
fun IntArray.swap(i: Int, j: Int) {
val temp = this[i]
this[i] = this[j]
this[j] = temp
}
tailrec fun mrUnrank1(rank: Int, n: Int, vec: IntArray) {
if (n < 1) return
val q = rank / n
val r = rank % n
vec.swap(r, n - 1)
mrUnrank1(q, n - 1, vec)
}
fun mrRank1(n: Int, vec: IntArray, inv: IntArray): Int {
if (n < 2) return 0
val s = vec[n - 1]
vec.swap(n - 1, inv[n - 1])
inv.swap(s, n - 1)
return s + n * mrRank1(n - 1, vec, inv)
}
fun getPermutation(rank: Int, n: Int, vec: IntArray) {
for (i in 0 until n) vec[i] = i
mrUnrank1(rank, n, vec)
}
fun getRank(n: Int, vec: IntArray): Int {
val v = IntArray(n)
val inv = IntArray(n)
for (i in 0 until n) {
v[i] = vec[i]
inv[vec[i]] = i
}
return mrRank1(n, v, inv)
}
fun main(args: Array<String>) {
var tv = IntArray(3)
for (r in 0..5) {
getPermutation(r, 3, tv)
System.out.printf("%2d -> %s -> %d\n", r, tv.contentToString(), getRank(3, tv))
}
println()
tv = IntArray(4)
for (r in 0..23) {
getPermutation(r, 4, tv)
System.out.printf("%2d -> %s -> %d\n", r, tv.contentToString(), getRank(4, tv))
}
println()
tv = IntArray(12)
val a = IntArray(4)
val rand = Random()
val fact12 = (2..12).fold(1) { acc, i -> acc * i }
for (i in 0..3) a[i] = rand.nextInt(fact12)
for (r in a) {
getPermutation(r, 12, tv)
System.out.printf("%9d -> %s -> %d\n", r, tv.contentToString(), getRank(12, tv))
}
}</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
323620184 -> [9, 2, 4, 5, 1, 7, 3, 10, 6, 11, 0, 8] -> 323620184
100091296 -> [2, 10, 6, 9, 5, 0, 3, 8, 1, 7, 11, 4] -> 100091296
310989081 -> [8, 10, 0, 6, 2, 5, 3, 1, 4, 7, 11, 9] -> 310989081
259044329 -> [6, 1, 3, 8, 4, 9, 2, 11, 10, 7, 0, 5] -> 259044329
</pre>
| |||