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


var johnsonTrotter = Fn.new { |n|
    var p = List.filled(n, 0)  // permutation
    var q = List.filled(n, 0)  // inverse permutation
    for (i in 0...n) p[i] = q[i] = i
    var d = List.filled(n, -1) // direction = 1 or -1
    var sign = 1
    var perms = []
    var signs = []
 
    var permute // recursive closure
    permute = Fn.new { |k|
        if (k >= n) {
            perms.add(p.toList)
            signs.add(sign)
            sign = sign * -1
            return
        }
        permute.call(k + 1)
        for (i in 0...k) {
            var z = p[q[k] + d[k]]
            p[q[k]] = z
            p[q[k] + d[k]] = k
            q[z] = q[k]
            q[k] = q[k] + d[k]
            permute.call(k + 1)
        }
        d[k] = d[k] * -1
    }
    permute.call(0)
    return [perms, signs]
}
 
var printPermsAndSigns = Fn.new { |perms, signs|
    var i = 0
    for (perm in perms) {
        System.print("%(perm) -> sign = %(signs[i])")
        i = i + 1
    }
}
 
var res = johnsonTrotter.call(3)
var perms = res[0]
var signs = res[1]
printPermsAndSigns.call(perms, signs)
System.print()
res = johnsonTrotter.call(4)
perms = res[0]
signs = res[1]
printPermsAndSigns.call(perms, signs)