Steinhaus-Johnson-Trotter algorithm

The Steinhaus-Johnson-Trotter algorithm or Johnson-Trotter algorithm is an algorithm which generates permutations by transposing elements.

Algorithm

The algorithm is setup with the idea that only one set of neighbors needs to swap positions and that there need only be 1 swap to generate the next permutation. To accommodate this, there needs to be an extra data element added: direction of mobility (ie direction of the swap). This direction is either left or right, but is initialized to the left. Pseudocode:

Initialize the first permutation 1 2 ... "n" all mobile to the left while there exists a mobile integer find the largest mobile integer "k" swap "k" and the adjacent integer in the direction of "k"'s mobility for each integer "l" if "l" > "k" then reverse the direction of mobility of "l"

An integer is said to be mobile if, in the direction of its mobility, the nearest integer is less than the current integer. Note that if an integer is to the far left and its mobility is to the left, it is not mobile. Similarly, if an integer is to the far right and its mobility is to the right, it is also not mobile.

=Example: n=3=

Using the Steinhaus-Johnson-Trotter algorithm with n = 3 would result in the following: <1 <2 <3 <1 <3 <2 <3 <1 <2 3> <2 <1 <2 3> <1 <2 <1 3>Note that this hits all 6 permutations.

=Example: n=4=

Using the Steinhaus-Johnson-Trotter algorithm with n = 4 would result in the following: <1 <2 <3 <4 <1 <2 <4 <3 <1 <4 <2 <3 <4 <1 <2 <3 4> <1 <3 <2 <1 4> <3 <2 <1 <3 4> <2 <1 <3 <2 4> <3 <1 <2 <4 <3 <1 <4 <2 <3 <4 <1 <2 <4 <3 <1 <2 4> 3> <2 <1 3> 4> <2 <1 3> <2 4> <1 3> <2 <1 4> <2 3> <1 <4 <2 3> <4 <1 <2 <4 3> <1 <4 <2 3> <1 4> <2 <1 3> <2 4> <1 3> <2 <1 4> 3> <2 <1 3> 4>Note that this hits all 24 permutations

ee also

* Fisher-Yates shuffle

External links

* [http://www.theory.csc.uvic.ca/%7Ecos/inf/perm/PermInfo.html Implementation of the Steinhaus-Johnson-Trotter algorithm]
* [http://www.cut-the-knot.org/Curriculum/Combinatorics/JohnsonTrotter.shtml Counting And Listing All Permutations: Johnson-Trotter Method] at cut-the-knot

References

*