Krishna Bharadwaj

Geek, Programmer, FOSS Enthusiast, CS grad student @ USC. Previously - Co-founded SMERGERS & Refer a Geek. Worked with National Instruments and BlockBeacon. Ex-Microsoft Student Partner. Loves Python / Django
More about me here.

Johnson Trotter Algorithm to generate Permutations! 29-May-2008

Johnson trotter algorithm gives a non recursive approach to generate permutations. The algorithm goes something like this..

while there exists a mobile integer k do
-->find the largest mobile integer k;
-->swap k and the adjacent integer its arrow points to;
-->reverse the direction of all integers that are larger than k

I'm using a character flag to maintain the direction of the mobile integers.. the code is simple, suggestions to make it more simple are always welcome

blog comments powered by Disqus