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


 
(lib 'list)
 
(for/fold (sign 1) ((σ (in-permutations 4)) (count 100)) 
    (printf "perm: %a count:%4d sign:%4d" σ count sign) (* sign -1))
 
perm: (0 1 2 3) count:   0 sign:   1
perm: (0 1 3 2) count:   1 sign:  -1
perm: (0 3 1 2) count:   2 sign:   1
perm: (3 0 1 2) count:   3 sign:  -1
perm: (3 0 2 1) count:   4 sign:   1
perm: (0 3 2 1) count:   5 sign:  -1
perm: (0 2 3 1) count:   6 sign:   1
perm: (0 2 1 3) count:   7 sign:  -1
perm: (2 0 1 3) count:   8 sign:   1
perm: (2 0 3 1) count:   9 sign:  -1
perm: (2 3 0 1) count:  10 sign:   1
perm: (3 2 0 1) count:  11 sign:  -1
perm: (3 2 1 0) count:  12 sign:   1
perm: (2 3 1 0) count:  13 sign:  -1
perm: (2 1 3 0) count:  14 sign:   1
perm: (2 1 0 3) count:  15 sign:  -1
perm: (1 2 0 3) count:  16 sign:   1
perm: (1 2 3 0) count:  17 sign:  -1
perm: (1 3 2 0) count:  18 sign:   1
perm: (3 1 2 0) count:  19 sign:  -1
perm: (3 1 0 2) count:  20 sign:   1
perm: (1 3 0 2) count:  21 sign:  -1
perm: (1 0 3 2) count:  22 sign:   1
perm: (1 0 2 3) count:  23 sign:  -1
 