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


      PROCperms(3)
      PRINT
      PROCperms(4)
      END
 
      DEF PROCperms(n%)
      LOCAL p%(), i%, k%, s%
      DIM p%(n%)
      FOR i% = 1 TO n%
        p%(i%) = -i%
      NEXT
      s% = 1
      REPEAT
        PRINT "Perm: [ ";
        FOR i% = 1 TO n%
          PRINT ;ABSp%(i%) " ";
        NEXT
        PRINT "] Sign: ";s%
        k% = 0
        FOR i% = 2 TO n%
          IF p%(i%)<0 IF ABSp%(i%)>ABSp%(i%-1) IF ABSp%(i%)>ABSp%(k%) k% = i%
        NEXT
        FOR i% = 1 TO n%-1
          IF p%(i%)>0 IF ABSp%(i%)>ABSp%(i%+1) IF ABSp%(i%)>ABSp%(k%) k% = i%
        NEXT
        IF k% THEN
          FOR i% = 1 TO n%
            IF ABSp%(i%)>ABSp%(k%) p%(i%) *= -1
          NEXT
          i% = k%+SGNp%(k%)
          SWAP p%(k%),p%(i%)
          s% = -s%
        ENDIF
      UNTIL k% = 0
      ENDPROC