Tropenhitze

Kannst du das spüren?

Steinhaus Johnson Trotter permutation algorithm explained and implemented in Java

with 36 comments

Johnson Trotter Algorithm

In this tutorial I’ve explained how this algorithm works. Please feel free to give your feedback and let me know if you want any other algorithm implemented.

About the algorithm

Given a positive integer n, this algorithm generates a list of permutations of {1, … , n} in non-lexicographical order.

i.e. given an input of 3, this algorithm would output

1 2 3
1 3 2
3 1 2
3 2 1
2 3 1
2 1 3

Terms used in this algorithm

Direction

First the numers 1…n are written in the increasing order and a direction is assigned to each of them which is initially LEFT. Note that the < symbol in front of each number below indicates that the direction associated with it is LEFT

<1 <2 <3

Similarly a number followed by > symbol would indicate that its direction is RIGHT. In the below example, number 3‘s direction is RIGHT.

3> <1 <2

Mobile integer

This algorithm uses a term called mobile integer. An integer is said to be mobile, if the adjacent number on its direction is smaller than this.

Note:-

If an integer is on the rightmost column pointing to the right, it’s not mobile.

If an integer is on the leftmost column pointing to the left, it’s not mobile.

The Algorithm

  1. The algorithm works by placing the numbers 1…n in the increasing order and associating LEFT < as the direction for each of them

  2. Find the largest mobile integer and swap it with the adjacent element on its direction without changing the direction of any of these two.

  3. In doing so, if the largest mobile integer has reached a spot where it’s no more mobile, proceed with the next largest integer if it’s mobile (or with the next …). There’s a catch. Read step 4.

  4. After each swapping, check if there’s any number, larger than the current largest mobile integer. If there’s one or more, change the direction of all of them. (see the example shown bellow for clarity).
  5. The algorithm terminates when there are no more mobile integers.

The Algorithm in action

1.  <1  <2  <3
2.  <1  <3  <2
3.  <3  <1  <2

Now 3 is no longer mobile as it’s in the leftmost column pointing to the left. Therefore proceed with the next largest mobile integer which is 2.

4.  3>  <2  <1

Now, number 3 has changed it’s direction due to step (iv) of the algorithm stated above. After three iterations in this step, as shown, when <2 was swapped with <1, the algorithm checks to see if there’s any number (not only mobile integers) larger than 2. Because there’s <3, it’s direction gets changed making it 3>

The algorithm now proceeds with 3> as it’s become the largest mobile integer again.

5.  <2  3>  <1
6.  <2  <1  3>

The algorithm terminates now as none of the integers are mobile any longer. The reason as to why they are not mobile is explained below.

<2 is no longer mobile as it’s on the leftmost column pointing to the left.
<1 is no longer mobile as there are no numbers on its direction smaller than itself.
3> is no longer mobile as it’s on the rightmost column pointing to the right.

Therefore the algorithm generates permutations in the non-lexicographical order as shown in steps 1 through 6 above.

Shown below is an example with n=4.

1.  <1  <2  <3  <4
2.  <1  <2  <4  <3
3.  <1  <4  <2  <3
4.  <4  <1  <2  <3

<4 is no longer mobile as it’s on the leftmost column pointing to the left. Swap <3 with <2 and change 4‘s direction to 4>

5.  4>  <1  <3  <2
6.  <1  4>  <3  <2
7.  <1  <3  4>  <2
8.  <1  <3  <2  4>

4> is no longer mobile as it’s on the rightmost column pointing to the right.  Swap <3 with <1 and change 4‘s direction to <4

9.  <3  <1  <2  <4
10. <3  <1  <4  <2
11. <3  <4  <1  <2
12. <4  <3  <1  <2

<4 is no longer mobile as it’s on the leftmost column pointing to the left
<3 is no longer mobile now as there’s no number smaller than itself on it’s direction
swap <2 with <1 and

(a)change 4‘s direction to 4>
(b)change 3‘s direction to 3>

Note that when a number is swapped, the direction of all those numbers that are larger than this number has to be changed

13. 4>  3>  <2  <1
14. 3>  4>  <2  <1
15. 3>  <2  4>  <1
16. 3>  <2  <1  4>

4 is no longer mobile as it’s on the rightmost column pointing to the right. Swap 3> with <2 and change 4‘s direction to <4

17. <2  3>  <1  <4
18. <2  3>  <4  <1
19. <2  <4  3>  <1
20. <4  <2  3>  <1

4 is no longer mobile as it’s on the leftmost column pointing to the left. Swap 3> with <1 and change 4‘s direction to 4>

21. 4>  <2  <1  3>
22. <2  4>  <1  3>
23. <2  <1  4>  3>
24. <2  <1  3>  4>

No numbers are mobile anymore (I hope you can understand why. If not, leave a comment and I’ll explain it too) and therefore the algorithm terminates after having generated 4!=24 permutations.

(I originally planned to publish my  Java implementation of this algorithm, which is unlike the  other quick and dirty types available across the web, but  later decided against it as I did not want my code copied elsewhere). However, upon reasonable request, I can provide you a password protected link to my code.

Please leave a comment if this tutorial was helpful to you, or if you’ve problems understanding this tutorial, or if you have any suggestion on improving this.

About these ads

36 Responses

Subscribe to comments with RSS.

  1. [...] Steinhaus Johnson Trotter permutation algorithm explained and implemented in Java [...]

  2. woOooo~ well explained on this algorithm :P thanks… but i’ve a question… this algorithm is based on factorial. basically, each number will have only one position at a time. but how about… for example… brute force? let say i’ve no 1, 2, 3 and 4. the possibility to have each number at different positions at a time can also happen. do i need to make a huge modification on this algorithm?

    fikri

    February 20, 2010 at 7:03 PM

  3. Can this algorithm be implemented using Multi-threading and find the time complexity … will it make a difference.

    Sha

    March 20, 2010 at 3:54 PM

    • I really doubt if this algorithm can be a good candidate for multi-threading. If you look at it, you’ll see that every stage represents a state which essentially follows the previous one (In order to arrive at stage 2, you need stage 1.. By “stages” here I mean one successful permutation.)
      However I need some time to think about any possibility of a multi-threaded implementation.

      The time complexity of this algorithm would depend upon how you implement it. (sounds strange doesn’t it?). Well, by implementation I mean, what kind of algorithm you use internally to keep track of positions and to make movements. I use a Tree data structure internally, but haven’t spent time to find out the time complexity. Will do it sometime later if you wish!

      Ragavan N

      March 21, 2010 at 2:34 PM

  4. can you give me the password to get the java code? The algo is explained very clearly here, thanks for that.

    Pranay

    July 29, 2010 at 6:37 AM

    • First of all thank you for your comment. But I have to say that I’m not interested in publishing the code as I might use it in the future for my own purposes and don’t want it copied elsewhere and be regarded plagiarized.

      Ragavan N

      July 29, 2010 at 10:36 AM

  5. I was breaking my head with this algo..The tutorial u gave s so clear.In the other links they have given the way alone and it was a bit confusing…If possible plz give me the java code for this algo.I am an M.E student and using this for my project.Plz hlp me sir.I assure that i vl not leak the code.
    Thank u in advance.

    Sindhu

    March 2, 2011 at 9:28 AM

    • You’re welcome. But I am not interested to share any code because I strongly believe one should enjoy the coding experience on his/her own. This algorithm is very challenging to implement and you’d thoroughly enjoy it doing so. Moreover, as I am planning to use my code for my projects later at some point of time, I am least interested in publishing it. Thanks for your understanding!

      Ragavan N

      March 2, 2011 at 9:58 AM

  6. Hey, my name is Scott and I am currently working on a Java implementation of the Johnston Trotter algorithm. However, I have run into some problems. I was just wondering if it would be possible for me to email you my code so that you could look at it and see what I am doing wrong. I am looking for someone to help me debug my code.

    Scott Gilday

    March 6, 2011 at 6:49 AM

    • You may e-mail to me the code on tropenhitze at gmail. I’ll have a look at it when I’m free and get back to you.

      Ragavan N

      March 6, 2011 at 4:47 PM

  7. Thank you very much for your clear explanation, this article helped me a lot to understand how the algorithm works. Cheers from Greece

    kostas

    April 17, 2011 at 7:49 PM

  8. thank by the explaination.
    it is very very clear, i’ll try to code this by my self.
    hi, from chile.

    cristian

    May 17, 2011 at 10:46 PM

    • Thanks to you too for your comments! :-) Have fun with coding! I appreciate it.

      Ragavan N

      May 18, 2011 at 12:32 AM

  9. wow the most wonderful tutorial

    Anonymous

    June 15, 2011 at 4:45 PM

  10. wow the most wonderful tutorial

    roba

    June 15, 2011 at 4:46 PM

  11. Please help me with my question. How do I find the position of any permutation in the Steinhaus Johnson Trotter permutation algorithm.
    For example, in your post, the permutation 2 4 3 1 in the 19-th i.e. it has position 19.

    newsun

    November 23, 2011 at 4:29 PM

  12. Many thanks for explaining this algorithm in such an easy way.
    Just need code it myself now with modifications.
    Thanks

    Hammad Rasheed

    January 31, 2012 at 1:02 PM

  13. can u get me the password for java code please>thanks for ur help|

    inzamam

    April 5, 2012 at 10:29 PM

  14. thanks man!!!!!!!!

    Anonymous

    April 15, 2012 at 2:43 PM

  15. My java program is no good past 9!. I don’t know how you could multithread it, but my intuition suggests the lexicographic approach could be made multithread. Next, I will convert the code into Python and see if it completes in a finite amount of time.

    Anonymous

    April 23, 2012 at 11:00 AM

  16. Excellent explanation, thanks! I’ve got a similar question to “newsun” above. Say I’ve got fifty elements, and I want to calculate the ten-million-million-millionth permutation in the series. Can I do that without visiting all the intermediate ones first?

    Anonymous

    April 25, 2012 at 12:23 PM

  17. [...] it’s frustrating to read that somebody implemented the Steinhaus–Johnson–Trotter algorithm to generate permutations but doesn’t [...]

    • I was interested in your implementation of the algotithm but i read that you are not sharing it with anybody.
      I wrote my own code but the computation goes too long for n=13 (approx 5-15 minutes) (due to expensive search for max mobile integer).
      Can you please post some of your results in terms of computational time? (only the computation with no printing).
      Thanks in advance.

      lawrencetb

      December 10, 2012 at 4:39 AM

  18. A very clear explanation illustrated with helpful examples. Thanks very much for this useful posting. Any chance you could deal with the location/pattern of odd and even permutations in this generating alogorithm.
    Vielen Dank!

    Ray

    January 9, 2013 at 3:22 AM

  19. good exaplanation thnkz a lot.i’ll try to code this because it feels interesting and challenging

    dil

    May 1, 2013 at 8:10 PM

  20. […] algorithm, I found very useful the pages Johnson-Trotter Algorithm Listing All Permutations and Steinhaus Johnson Trotter permutation algorithm explained and implemented in Java this algorithm is very efficient, only about 2 seconds to find all permutations, ie 10! = […]

  21. Your clear explanation helped me create a recursive SQL version of Steinhaus-Johnson-Trotter; thank you!

    http://it.toolbox.com/blogs/data-ruminations/tropical-heat-helps-generate-permutations-58048

    zoominations

    November 22, 2013 at 4:39 AM

    • Thank you very much for the kind words and for back-links from your blog. I appreciate your gesture. I wrote this almost 4 years ago on a day when I was very frustrated and had nothing else to do. It’s unbelievable how it’s helping people every day. This post has been consistently getting over 50 hits a day for the past 4 years.

      Ragavan N

      November 22, 2013 at 4:49 AM

  22. Why wouldn’t you just publish this kind of code. It’s not that you got paid by a company to do this. Sharing is caring. It’s also not something that would benefit you to keep it private, you may learn something by publishing your code and getting feedback.

    Article is wrriten nice though, hope you do something with the feedback ^^

    Sam Stoelinga

    December 8, 2013 at 1:57 PM

  23. Thanks for the plain english explanation. It allowed me to implement a C# version. If somebody would like a hint at a possible solution you can find the code at the location below. I hope you find it usefull.

    http://pastebin.com/vFmce4EP

    David

    December 19, 2013 at 10:23 PM

  24. Can you please explain at the end why the numbers are not mobile anymore? You explained the rest really well and I’m just confused about the final part. Do we know it’s the end because there’s already been 4!=24 permutations?

    Thank you

    Bob

    March 4, 2014 at 11:27 AM

    • Please see the explanation given for 3 numbers. You should be able to related it to this.

      Ragavan N

      March 4, 2014 at 2:58 PM

  25. That was nice and well explained. Thanks :D

    Anonymous

    March 31, 2014 at 5:07 AM

  26. super explained!!!!

    fdfdf

    May 6, 2014 at 11:30 AM


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: