24 lines
1.2 KiB
Plaintext
24 lines
1.2 KiB
Plaintext
;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 [[Matrix arithmetic|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 [[wp:Parity_of_a_permutation#Example|this]] discussion adjacency is not a requirement.
|
||
|
||
|
||
;References:
|
||
* [[wp:Steinhaus–Johnson–Trotter algorithm|Steinhaus–Johnson–Trotter algorithm]]
|
||
* [http://www.cut-the-knot.org/Curriculum/Combinatorics/JohnsonTrotter.shtml Johnson-Trotter Algorithm Listing All Permutations]
|
||
* [http://stackoverflow.com/a/29044942/10562 Correction to] Heap's algorithm as presented in Wikipedia and widely distributed.
|
||
* [http://www.gutenberg.org/files/18567/18567-h/18567-h.htm#ch7] Tintinnalogia
|
||
|
||
|
||
;Related tasks:
|
||
* [[Matrix arithmetic]]
|
||
* [[Gray code]]
|
||
<br><br>
|