Task

Generate permutations of n items in which successive permutations differ from each other by the swapping of any two items.

Also generate the sign of the permutation which is +1 when the permutation is generated from an even number of swaps from the initial state, and -1 for odd.

Show the permutations and signs of three items, in order of generation here.

Such data are of use in generating the determinant of a square matrix and any functions created should bear this in mind.

Note: The Steinhaus–Johnson–Trotter algorithm generates successive permutations where adjacent items are swapped, but from this discussion adjacency is not a requirement.



References

 Steinhaus–Johnson–Trotter algorithm
 Johnson-Trotter Algorithm Listing All Permutations
 Heap's algorithm
 [1] Tintinnalogia


Related tasks

   Matrix arithmetic
   Gray code


// Implementation of Heap's algorithm.
// See https://en.wikipedia.org/wiki/Heap%27s_algorithm#Details_of_the_algorithm
func generate<T>(array: inout [T], output: (_: [T], _: Int) -> Void) {
    let n = array.count
    var c = Array(repeating: 0, count: n)
    var i = 1
    var sign = 1
    output(array, sign)
    while i < n {
        if c[i] < i {
            if (i & 1) == 0 {
                array.swapAt(0, i)
            } else {
                array.swapAt(c[i], i)
            }
            sign = -sign
            output(array, sign)
            c[i] += 1
            i = 1
        } else {
            c[i] = 0
            i += 1
        }
    }
}
 
func printPermutation<T>(array: [T], sign: Int) {
    print("\(array) \(sign)")
}
 
print("Permutations and signs for three items:")
var a = [0, 1, 2]
generate(array: &a, output: printPermutation)
 
print("\nPermutations and signs for four items:")
var b = [0, 1, 2, 3]
generate(array: &b, output: printPermutation)