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


permutations: function [arr][
    d: 1
    c: array.of: size arr 0
    xs: new arr
    sign: 1
 
    ret: new @[@[xs, sign]]
 
    while [true][
        while [d > 1][
            d: d-1
            c\[d]: 0
        ]
 
        while [c\[d] >= d][
            d: d+1
            if d >= size arr -> return ret
        ]
 
        i: (1 = and d 1)? -> c\[d] -> 0
        tmp: xs\[i]
        xs\[i]: xs\[d]
        xs\[d]: tmp
 
        sign: neg sign
        'ret ++ @[new @[xs, sign]]
        c\[d]: c\[d] + 1
    ]
 
    return ret
]
 
loop permutations 0..2 'row ->
    print [row\0 "-> sign:" row\1]
 
print ""
 
loop permutations 0..3 'row ->
    print [row\0 "-> sign:" row\1]