Step by Step solution about How to resolve the algorithm Permutations by swapping step by step in the Kotlin programming language

Johnson-Trotter Algorithm

This code implements the Johnson-Trotter algorithm in Kotlin, which is an algorithm for generating all permutations of a set of elements. The algorithm maintains a permutation and its inverse, along with a direction (1 or -1) for each element. It iterates through the permutation, changing the direction of each element in turn and swapping it with its neighbor in the specified direction. This process continues until all permutations have been generated.

Function johnsonTrotter

• Input: n: The number of elements in the set.
• Output: A pair of lists: perms containing all permutations and signs indicating the sign of each permutation (-1 or 1).

Algorithm:

1. Initialize the permutation p and its inverse q to the identity permutation (e.g., p[0] = 0, p[1] = 1, etc.).
2. Initialize the direction d to -1 for all elements.
3. Set the sign sign to 1.
4. Initialize two mutable lists, perms and signs, to store the permutations and their signs.
5. Define a recursive function permute(k):
   • If k is greater than or equal to n, add the current permutation p and its sign to perms and signs respectively, and change the sign to -sign.
   • Recursively call permute(k + 1).
   • Loop through all indices i from 0 to k-1:
     • Find the index z such that p[q[k] + d[k]] = z.
     • Swap p[q[k]] with p[q[k] + d[k]].
     • Update q[z] to be q[k] and update q[k] by adding d[k].
     • Recursively call permute(k + 1).
   • Change the direction d[k] to -d[k].
6. Call permute(0) to start the recursion.

Function printPermsAndSigns

• Input: perms: List of permutations.
• Input: signs: List of signs corresponding to each permutation.
• Output: Prints each permutation along with its sign.

Main Function

• Calls johnsonTrotter(3) and prints the permutations and signs for n = 3.
• Calls johnsonTrotter(4) and prints the permutations and signs for n = 4.

// version 1.1.2

fun johnsonTrotter(n: Int): Pair<List<IntArray>, List<Int>> {
    val p = IntArray(n) { it }  // permutation
    val q = IntArray(n) { it }  // inverse permutation
    val d = IntArray(n) { -1 }  // direction = 1 or -1
    var sign = 1
    val perms = mutableListOf<IntArray>()
    val signs = mutableListOf<Int>()

    fun permute(k: Int) {
        if (k >= n) {
            perms.add(p.copyOf())
            signs.add(sign)
            sign *= -1
            return
        } 
        permute(k + 1)
        for (i in 0 until k) {
            val z = p[q[k] + d[k]]
            p[q[k]] = z
            p[q[k] + d[k]] = k
            q[z] = q[k]
            q[k] += d[k]
            permute(k + 1)
        }
        d[k] *= -1
    } 

    permute(0)
    return perms to signs
}

fun printPermsAndSigns(perms: List<IntArray>, signs: List<Int>) {
    for ((i, perm) in perms.withIndex()) {
        println("${perm.contentToString()} -> sign = ${signs[i]}")
    }
}

fun main(args: Array<String>) {
    val (perms, signs) = johnsonTrotter(3)
    printPermsAndSigns(perms, signs)
    println()
    val (perms2, signs2) = johnsonTrotter(4)
    printPermsAndSigns(perms2, signs2)
}