25 lines
1.1 KiB
Text
25 lines
1.1 KiB
Text
|
;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]
|
|||
|
|
* [[wp:Heap's algorithm|Heap's algorithm]]
|
|||
|
|
* [http://www.gutenberg.org/files/18567/18567-h/18567-h.htm#ch7] Tintinnalogia
|
|||
|
|
|
|||
|
|
|
|||
|
|
;Related tasks:
|
|||
|
|
* [[Matrix arithmetic]]
|
|||
|
|
* [[Gray code]]
|
|||
|
|
<br><br>
|
|||
|
|
|