Step by Step solution about How to resolve the algorithm Permutations/Rank of a permutation step by step in the Kotlin programming language

This Kotlin code implements two algorithms for permutations: mrUnrank1 and mrRank1. Permutations are used in various mathematical and computational applications, including combinatorics, optimization, and cryptography.

mrUnrank1

The mrUnrank1 function takes as input a rank, a size, and a vector, and generates the corresponding permutation. The rank represents a specific permutation within the set of all possible permutations of the given size. The function works by iteratively swapping elements in the vector to obtain the desired permutation.

It follows a recursive approach, based on the mathematical definition of unranking. It unranks a permutation by recursively swapping elements in the vector until the desired rank is achieved.

mrRank1

The mrRank1 function takes as input a vector representing a permutation, and returns its rank. The rank is the index of the permutation within the set of all possible permutations of the given size.

It also follows a recursive approach, based on the mathematical definition of ranking. It ranks a permutation by recursively swapping elements in the vector and computing the rank at each step.

getPermutation

The getPermutation function generates a permutation for a given rank and size. It initializes a vector with the numbers from 0 to size-1, and then calls mrUnrank1 to generate the desired permutation.

getRank

The getRank function returns the rank of a given permutation. It takes as input a vector representing the permutation, and calls mrRank1 to compute the rank.

Usage

The main function demonstrates the usage of these functions by generating and printing permutations for different ranks and sizes. It also generates random ranks for a size of 12 and displays the corresponding permutations and ranks. This illustrates the relationship between ranks and permutations.

Example Output

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

0 -> [0, 1, 2, 3] -> 0
1 -> [0, 1, 3, 2] -> 1
2 -> [0, 2, 1, 3] -> 2
3 -> [0, 2, 3, 1] -> 3
4 -> [0, 3, 1, 2] -> 4
5 -> [0, 3, 2, 1] -> 5
6 -> [1, 0, 2, 3] -> 6
7 -> [1, 0, 3, 2] -> 7
8 -> [1, 2, 0, 3] -> 8
9 -> [1, 2, 3, 0] -> 9
10 -> [1, 3, 0, 2] -> 10
11 -> [1, 3, 2, 0] -> 11
12 -> [2, 0, 1, 3] -> 12
13 -> [2, 0, 3, 1] -> 13
14 -> [2, 1, 0, 3] -> 14
15 -> [2, 1, 3, 0] -> 15
16 -> [2, 3, 0, 1] -> 16
17 -> [2, 3, 1, 0] -> 17
18 -> [3, 0, 1, 2] -> 18
19 -> [3, 0, 2, 1] -> 19
20 -> [3, 1, 0, 2] -> 20
21 -> [3, 1, 2, 0] -> 21
22 -> [3, 2, 0, 1] -> 22
23 -> [3, 2, 1, 0] -> 23

68993488 -> [7, 4, 1, 0, 5, 3, 6, 9, 8, 2, 10, 11] -> 68993488
26592411 -> [2, 9, 0, 1, 5, 3, 6, 11, 8, 7, 10, 4] -> 26592411
31281156 -> [5, 3, 9, 6, 0, 8, 2, 7, 4, 1, 10, 11] -> 31281156
25290392 -> [11, 4, 3, 6, 5, 0, 1, 8, 2, 9, 7, 10] -> 25290392

// 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))
    }
}