Help with Lexicographic Permutations - (Problem 90)

Christopher, Hi!

You are right, with N=12 the total amount of possible permutations is over 400 millions and if we multiply it by at least 12 bytes for each, this yields at least 5 Gb of memory.

So probably building the full list (with the aim of sorting it then?) is bit tricky.

One idea is that we need not full list. If you simply generate them in lexicographic order (starting from very first which is ABCDE...) you at each step only need previous one to build the next one. So memory is only necessary to keep one permutation and its index.

This approach has one sad property - building these millions of permutations will take significant time. With modern hardware I believe in Python it is possible to do about a million of such iterations per second - so it may take few minutes. (But for larger N this will become a real problem)

So yet another approach is simply to convert the required index into permutation. This could be done if you represent index in factorial system rather decimal or hexadecimal. The same wiki article has a link to this page which, I believe, can help if you are curious about this approach.

Hope this helps - and feel free to ask more about details or anything!

Rodion