1
$\begingroup$

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!:

enter image description here

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?

$\endgroup$
2
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ sounds promising but you lost me towards the end. would you mind to include annotations next to each relevant permutation ? $\endgroup$ – amphibient Aug 21 '15 at 21:02
  • 2
    $\begingroup$ Well, just as an example: Take 2143. In this case $mn$ is the string 14. In this case we bump up $m$ by 1 to get 2, but that already appears to the left of $m$, so we bump up again to 3. So now we have 23??. We replace the question marks by the numbers we haven't listed yet, in increasing order. So we get 2314. $\endgroup$ – frakbak Aug 21 '15 at 21:06
  • 2
    $\begingroup$ A more complicated example: 524631. Here we have to bump the 4 up to 6, and then list the remaining numbers in increasing order. So we get 526134. $\endgroup$ – frakbak Aug 21 '15 at 21:08
  • $\begingroup$ how do you get 23 if you increment 1 in 14 twice ? wouldn't you get 34 ? $\endgroup$ – amphibient Aug 21 '15 at 21:13
  • 1
    $\begingroup$ The starting permutation is 2143. Since here $mn$ is the string 14, I'm going to replace this string and everything following it by something new. So my new permutation will look like 2???. The algorithm says to replace the first question mark by the next possible whole number which is greater than $m=1$ (next possible, i.e. we're not allowed to have repetitions in a permutation). Since 2 is there already written down in the new permutation, we have to go with 3. That's why we get 23??. $\endgroup$ – frakbak Aug 21 '15 at 21:18
1
$\begingroup$

You can easily implement a recursive algorithm. Let the function $perm(n)$ return the set of all permutations of $\{1,2,\cdots,n\}$. Then if you have generated $perm(n-1)$, you can get $perm(n)$ by inserting $n$ into any permutation from $perm(n-1)$ into any position. For example if $n=4$, then a possible permutation for $n=3$ is $213$, so this will generate: $4213,2413,2143,2134$.

$\endgroup$
  • $\begingroup$ yes but can you do that under the limitations i set forth: doing it manually ? $\endgroup$ – amphibient Aug 21 '15 at 20:56
  • $\begingroup$ see my last paragraph after the image $\endgroup$ – amphibient Aug 21 '15 at 21:00
  • $\begingroup$ BTW, the recursive algorithm, when implemented, runs out of memory at about a length of 11 elements $\endgroup$ – amphibient Aug 21 '15 at 21:01
  • $\begingroup$ The recursive algorithm can be carried out manually, with pencil-and-paper. The key is recognizing the "tail" of the sequence where the algorithm has "terminated", namely the longest terminal descending sequence. @frakbak 's write-up gives one description of how to recognize this, "find the last pair of consecutive numbers" which are in increasing order. $\endgroup$ – hardmath Aug 22 '15 at 14:13
  • $\begingroup$ @amphibient The only thing required by this recursion is the list of permutations of the first $n-1$ elements. If you "run out of memory" while computing this, how are you going to present the list of all $N!$ permutations to the ancient Greek ruler so he can check them for correctness (or have them checked) and decide whether to reward you? The partially-finished written list of permutations is all the memory storage you need. $\endgroup$ – David K Aug 22 '15 at 15:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.