Step by Step solution about How to resolve the algorithm Superpermutation minimisation step by step in the Go programming language

• The program generates superpermutations of length n for n between 0 and 11.

• A superpermutation is a permutation of all the integers from 1 to n such that the numbers in the permutation are themselves permutations.

• For example, the superpermutation of length 3 is 213, which is a permutation of 1, 2, and 3, and the numbers 2 and 13 are also permutations of 1, 2, and 3.

• The program uses a recursive function, r(), to generate the superpermutations.

  • The function r() takes an integer n as input and returns a boolean value.

  • The function r() starts by checking if n is equal to 0. If n is equal to 0, the function returns false.

  • If n is not equal to 0, the function gets the value of the nth element in the super array and decrements the count of the nth element in the cnt array.

  • If the count of the nth element in the cnt array is now equal to 0, the function sets the count of the nth element in the cnt array to n and calls the function r() recursively with n-1 as the input.

  • If the function r() returns false, the function r() returns false.

  • If the function r() returns true, the function sets the nth element in the super array to the value of the nth element in the cnt array and increments the pos variable by 1.

  • The function r() then returns true.

• The program uses a function, superperm(), to generate the superpermutations.

  • The function superperm() takes an integer n as input.

  • The function superperm() starts by setting the pos variable to n.

  • The function superperm() then calculates the length of the super array using the factSum() function.

  • The function superperm() then creates a slice of bytes with a length equal to the length of the super array.

  • The function superperm() then initialises the cnt array with the values from 0 to n.

  • The function superperm() then initialises the super array with the values from 1 to n.

  • The function superperm() then calls the function r() with n as the input.

  • The function superperm() then prints the length of the super array.

• Main Function:

  • The main function calls the superperm() function for n between 0 and 11 and prints the length of the super array for each n.

package main

import "fmt"

const max = 12

var (
    super []byte
    pos   int
    cnt   [max]int
)

// 1! + 2! + ... + n!
func factSum(n int) int {
    s := 0
    for x, f := 0, 1; x < n; {
        x++
        f *= x
        s += f
    }
    return s
}

func r(n int) bool {
    if n == 0 {
        return false
    }
    c := super[pos-n]
    cnt[n]--
    if cnt[n] == 0 {
        cnt[n] = n
        if !r(n - 1) {
            return false
        }
    }
    super[pos] = c
    pos++
    return true
}

func superperm(n int) {
    pos = n
    le := factSum(n)
    super = make([]byte, le)
    for i := 0; i <= n; i++ {
        cnt[i] = i
    }
    for i := 1; i <= n; i++ {
        super[i-1] = byte(i) + '0'
    }

    for r(n) {
    }
}

func main() {
    for n := 0; n < max; n++ {
        fmt.Printf("superperm(%2d) ", n)
        superperm(n)
        fmt.Printf("len = %d\n", len(super))
    }
}