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


' version 31-03-2017
' compile with: fbc -s console
 
Sub perms(n As ULong)
 
    Dim As Long p(n), i, k, s = 1
 
    For i = 1 To n
        p(i) = -i
    Next
 
    Do
        Print "Perm: [ ";
        For i = 1 To n
            Print Abs(p(i)); " ";
        Next
        Print "] Sign: "; s
 
        k = 0
        For i = 2 To n
            If p(i) < 0 Then
                If Abs(p(i)) > Abs(p(i -1)) Then
                    If Abs(p(i)) > Abs(p(k)) Then k = i
                End If
            End If
        Next
 
        For i = 1 To n -1
            If p(i) > 0 Then
                If Abs(p(i)) > Abs(p(i +1)) Then
                    If Abs(p(i)) > Abs(p(k)) Then k = i
                End If
            End If
        Next
 
        If k Then
            For  i = 1 To n
                If Abs(p(i)) > Abs(p(k)) Then p(i) = -p(i)
            Next
            i = k + Sgn(p(k))
            Swap p(k), p(i)
            s = -s
        End If
 
    Loop Until k = 0
 
End Sub
 
' ------=< MAIN >=------
 
perms(3)
print
perms(4)
 
' empty keyboard buffer
While Inkey <> "" : Wend
Print : Print "hit any key to end program"
Sleep
End
 