Non-recursively generating permutations
Saturday, October 15th, 2005A cool link:
In essence the algorithm works as follows:
1. start looking from the end of the sequence for two consecutive values i and ii such that i < ii.
2. start looking from the end of the sequence for the value j greater that i (the worst case getting ii or earlier).
3. swap i and j
4. reverse the sequence ii to last.
Examples:
123 -> i = 2, ii = 3, j = 3 -> 132
132 -> i=1,ii=2,j=3 -> 213
213 -> i=2;ii=3;j=3 -> 231
231 -> i=1;ii=2;j=2 -> 312
312 -> i=2;ii=3;j=3 -> 321
321 – END
It also generates only unique permutations if there are some duplicates in the sequence (e.g. AAABBB) Cool!