Non-recursively generating permutations
A cool link: http://www.dogma.net/markn/articles/Permutations/
In essence the algorithm works as follows:
- start looking from the end of the sequence for two consecutive values i and ii such that i < ii.
- start looking from the end of the sequence for the value j greater that i (the worst case getting ii or earlier).
- swap i and j
- 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!