Permutations in lexicographic order

algorithmsintuitionpermutations

A permutation is a bijection from a set to itself.

$$\pi: \{1,\ldots , n\} \mapsto \{1,\ldots , n\}$$

One way to get permutations in lexicographic order is based on the algorithm successor which finds each time the next permutation.

This procedure works as follows:

  • We start from the end of the list and we find the first number that is smaller from its next one, say $x$.

  • Then we start again from the end of the list and we find the first number that is bigger than $x$, say $y$.

  • We replace $x$ and $y$.

  • We reverse the sublist that starts from the next position of (the new position) of $y$ till the end.

The algorithm is :

enter image description here

I haven't really understood the idea of that algorithm. Could you explain that further to me? Do we change the order of the elements at the end of the list to get the next permutation in lexicographic order?

$$$$

Other methods to get get permutations in lexicographic order is with rank and unrank.

These algorithms are:

enter image description here

enter image description here

Is the idea of these ones that we write all the permutations in lexicograhic order and enumerate them to get the rank and the unrank is, given a number (rank), that we can give the respective permutation?

Is that correct? Or is the idea of rank or unrank related to permutations elsewise?

$$$$

EDIT :

I am trying to understand the formula that is used in permLexRank(n,L).

The formula is $$\text{rank}(\pi,n)=(\pi(1)-1)(n-1)!+\text{rank}(\pi',n-1) \ \text{ with } \ \text{rank}([1],1)=0$$ where $\pi'$ is the permutation that we get if at $\pi$ we delete the first element and subtract all elements that are greater than that by $1$.

The idea for this formula is : At the lexicographic order of permutations of $S=\{1,\ldots n\}$ first there are $(n-1)!$ permutations that start by $1$ then there are $(n-1)!$ permutations that start by $2$, etc.

So it holds that $$(\pi(1)-1)(n-1)!\leq \text{rank}(\pi)\leq \pi(1)(n-1)!-1$$
If $r'$ is the rank of $\pi$ in the set of $(n-1)!$ permutations that start with $\pi(1)$, then $r'$ is the rank of $[\pi(2), \ldots , \pi(n)]$ if we conside it as a permutation of $\{1, \ldots , n\}\setminus \{\pi(1)\}$.

If we subtract each element of $[\pi(2), \ldots , \pi(n)]$ by $1$ we get a permutation $\pi'$ of $\{1, \ldots , n-1\}$ that has again rank $r'$.

I haven't really understood that. Could you explain that to me?

Best Answer

When it comes to understanding the pseudocode, one of method is to run a non-trivial example to see how it works. Obviously, it is not a proof, but it is rather to see the mechanics. Here I believe, indexing starts with 0. Run the following steps on your favorite example and see what is happening (for instance [a, c, b] and n=3 or [z, b, a, k, d] and n=5 etc.)

When it comes to theoretical understanding step by step.

Firstly, you inspect index i. The idea is to find a place in your sequence such that all elements from i until n-2 are sorted in decreasing order. You can see that because you decrease i only when the element on right is smaller. You remember i as your pivot index. If i is at the beginning of the array, it means that the whole array is (almost) sorted.

Then you work with j index. It starts with n-1 element (the last one) but it goes all the way down and ensures that all elements from j until the end of array are smaller than pivot. Notice that j is always larger than i.

Then we do swap of L[j] and L[i]. Notice that usually j = i+1 (when not?)

Then it is convenient to realize that (n - (i+1))//2 + 1 is just halfway through between n and i+1. And these swaps in for loop is just reflecting the whole array around this axis (so changing the order, take [10, 3, 2, 1, 0] and n=5, i=1 (so k is running from 1 to 2 and swapping L[2]=3 and L[4]=0 and L[3]=2 and L[2]=1 to obtain [10, 0, 1, 2, 3].

Related Question