I am looking to find if there is a way to manually (meaning, not using a machine that has high memory capacity) generate all the permutations of a set of N non-repeating (unique) elements by the way of an elegant (lightweight) algorithm that relies on swapping elements from the last established permutation. I am aware that it is possible to do it programmatically, however, all the solutions I have come across are basically impossible to reproduce manually because they rely on storing large amounts of subset permutations in memory, which is not possible under human cognitive limitations.
It is well known that a set of unique elements (1, 2, 3,..., N) has N! possible permutations. So a set of 4 will have 24 possible permutations but a set of 7 will have 5040.
I am trying to see if there is an algorithm that would not require considering more than a single previous permutation (hopefully the most immediate previous one) in order to come up with the next unique one. So I tried starting with the initial sequence and moving the last element one index to the left. Unfortunately, I arrived to a duplicate before I exhausted N!:
Let's say that you were a mathematician in Ancient Greece and a local ruler offered you as many drachmas as there are permutations of, say a set of 8 elements (40320 total) to write them all in order and, of course, you didn't have a machine to solve it programmatically, is there a way to establish a routine that could be repeated from one permutation to the next, starting with the original order, that would ensure no duplicates yet cover all the possible permutations?
Best Answer
Yes. Start with the permutation which lists the numbers $1$ through $N$ in increasing order. Then repeatedly do the following: In the permutation you have, find the last pair of consecutive numbers in which the latter is greater than the former (if there is no such pair, stop, you're done). Call this pair $mn$. Increase $m$ by $1$ until you get a number $m'$ that does not appear prior to $m$. Then list the remaining (not yet listed) numbers after $m'$ in increasing order.
Example:
1234
1243
1324
1342
1423
1432
2134
2143
2314
2341
2413
2431
3124
3142
3214
3241
3412
3421
4123
4132
4213
4231
4312
4321