user
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
assistant
(formerly Perl 6)

### Recursive

**Works with**: rakudo version 2015-09-25

```
sub insert($x, @xs) { ([flat @xs[0 ..^ $_], $x, @xs[$_ .. *]] for 0 .. +@xs) }
sub order($sg, @xs) { $sg > 0 ?? @xs !! @xs.reverse }
 
multi perms([]) {
    [] => +1
}
 
multi perms([$x, *@xs]) {
    perms(@xs).map({ |order($_.value, insert($x, $_.key)) }) Z=> |(+1,-1) xx *
}
 
.say for perms([0..2]);

```

Output:

```
[0 1 2] => 1
[1 0 2] => -1
[1 2 0] => 1
[2 1 0] => -1
[2 0 1] => 1
[0 2 1] => -1
```