Steinhaus–Johnson–Trotter implementation in Java

Generally it’s frustrating to read that somebody implemented the Steinhaus–Johnson–Trotter algorithm to generate permutations but doesn’t supply the source code due to the fear that the code could be “copied elsewhere” on the internet. Since I was really interested in permutations for another project I implemented the said algorithm, added a LGPL license to it and published it.

You can have a look at the code here.

The algorithm

If you came this far it’s likely that you’ve already read the corresponding article on Wikipedia and understood the inner workings of the algorithm in detail. All that’s missing is how to implement it. I’ve provided the source code in Java and it should be really straight forward to transform this into another similar language like C/C++, Python, Perl or the like.

Just take your time trying it out on paper or commenting in the output method I provided in my implementation to see the exact steps of the implementation. This should definitely help you understanding how all this works. Running the Java code in the debugger and stepping through the code would be another nice option to study what’s happening.

Conclusion

I find permutations quite interesting because they can be used in various scenarios. One aspect is that as a developer it may help you to understand all the different possibilities a defined input set may look like – this is particularly helpful if you’re analyzing which input a user might enter into your application and whether you’ve thought of all different variants.

On a final note I really want to encourage everybody who’s written some nice piece of code to publish it under a certain license. Whether this may be the GPL or a more liberal one like the BSD is up to you but for the sake of helping others grow publish what you’ve done so everybody else can study it. Maybe somebody finds a mistake and helps you this way as well.