Steinhaus-Johnson-Trotter algorithm

From Wikipedia, the free encyclopedia

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

1 Algorithm
- 1.1 Example: n=3
- 1.2 Example: n=4
2 See also
3 External links
4 References

[edit] 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.

[edit] 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.

[edit] 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