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 output([Object[]]$A, [Int]$k, [ref]$sign) 
{
    "Perm: [$([String]::Join(', ', $A))] Sign: $($sign.Value)"
}
 
function permutation([Object[]]$array)
{
    function generate([Object[]]$A, [Int]$k, [ref]$sign) 
    {
        if($k -eq 1) 
        {
            output $A $k $sign
            $sign.Value = -$sign.Value
        }
        else
        {
            $k -= 1
            generate $A  $k $sign
            for([Int]$i = 0; $i -lt $k; $i += 1)
             {
                if($i % 2 -eq 0)
                {
                    $A[$i], $A[$k] = $A[$k], $A[$i]
                }
                else
                {
                    $A[0], $A[$k] = $A[$k], $A[0]
                }
                generate $A $k $sign
            }
        }
    }
    generate $array $array.Count ([ref]1)
}
permutation @(0, 1, 2)
""
permutation @(0, 1, 2, 3)
 