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


call perms(3)
print
call perms(4)
end
 
subroutine perms(n)
    dim p((n+1)*4)
    for i = 1 to n
        p[i] = -i
    next i
    s = 1
 
    do
        print "Perm: [ ";
        for i = 1 to n
            print abs(p[i]); " ";
        next i
        print "] Sign: "; s
 
        k = 0
        for i = 2 to n
            if p[i] < 0 and (abs(p[i]) > abs(p[i-1])) and (abs(p[i]) > abs(p[k])) then k = i
        next i
        for i = 1 to n-1
            if p[i] > 0 and (abs(p[i]) > abs(p[i+1])) and (abs(p[i]) > abs(p[k])) then k = i
        next i
        if k then
            for i = 1 to n    #reverse elements > k
                if abs(p[i]) > abs(p[k]) then p[i] = -p[i]
            next i
            if p[k] < 0 then i = k-1 else i = k+1
            temp = p[k]
            p[k] = p[i]
            p[i] = temp
            s = -s
        end if
    until k = 0
end subroutine