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


function spermutations(integer p, integer i)
--
-- generate the i'th permutation of [1..p]:
-- first obtain the appropriate permutation of [1..p-1],
-- then insert p/move it down k(=0..p-1) places from the end.
--  
    sequence res
    integer k = mod(i-1,2*p)
    if k>=p then k=2*p-1-k  end if
    if p>1 then
        res = spermutations(p-1,floor((i-1)/p)+1)
        res = res[1..length(res)-k]&p&res[length(res)-k+1..$]
    else
        res = {1}
    end if
    return res
end function
 
for p=1 to 4 do
    printf(1,"==%d==\n",p)
    for i=1 to factorial(p) do
        integer parity = iff(and_bits(i,1)?1:-1)
        ?{i,spermutations(p,i),parity}
    end for
end for
