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


include c:\cxpl\codes;
 
proc PERMS(N);
int  N;                         \number of elements
int  I, K, S, T, P;
[P:= Reserve((N+1)*4);
for I:= 0 to N do P(I):= -I;    \initialize facing left (also set P(0)=0)
S:= 1;
repeat  Text(0, "Perm: [ ");
        for I:= 1 to N do
                [IntOut(0, abs(P(I)));  ChOut(0, ^ )];
        Text(0, "] Sign: ");  IntOut(0, S);  CrLf(0);
 
        K:= 0;                  \find largest mobile element
        for I:= 2 to N do                         \for left-facing elements
            if P(I) < 0 and
                abs(P(I)) > abs(P(I-1)) and       \ greater than neighbor
                abs(P(I)) > abs(P(K)) then K:= I; \ get largest element
        for I:= 1 to N-1 do                       \for right-facing elements
            if P(I) > 0 and
                abs(P(I)) > abs(P(I+1)) and       \ greater than neighbor
                abs(P(I)) > abs(P(K)) then K:= I; \ get largest element
        if K # 0 then           \mobile element found
           [for I:= 1 to N do   \reverse elements > K
                if abs(P(I)) > abs(P(K)) then P(I):= P(I)*-1;
            I:= K + (if P(K)<0 then -1 else 1);
            T:= P(K);  P(K):= P(I);  P(I):= T;    \swap K with element looked at
            S:= -S;             \alternate signs
            ];
until   K = 0;                  \no mobile element remains
];
 
[PERMS(3);
CrLf(0);
PERMS(4);
]