Permutations in lexicographic order 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 :

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:


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?
 A: 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].
A: As I understood, the algorithm PermLexSuccessor(n,L), given a permutation $L$ of numbers $1,\dots,n-1$ constructs a permutation which is lexicographically next to $L$. To feel how it works we can take the identity permutation for some small $n$ (say $4$ or $5$), and consecutively applying the algorithm, to obtains the list of all permutations of numbers $1,\dots,n-1$ in the lexicographic order.

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?

As I understood, given $n$, the algorithms permLexRank(n,L) and permLexRank(n,r) provide an enumeration $e:S\to \{0,\dots, (n+1)!-1\}$ of a set $S$ of all bijections between sets $\{0,1,\dots, n\}$ and $\{1,\dots, n+1\}$. Namely, given $L\in S$, the algorithm permLexRank(n,L) calculates $e(S)$, and given an integer $r\in \{0,\dots, (n+1)!-1\}$, the algorithm permLexRank(n,r) constructs $e^{-1}(r)$.
A: For an outline of the proof/working of the first algorithm (permLexSuccessor), you can refer to this post on cs.stackexchange:
("Correctness proof of the algoritm to generate permutations in lexicographic order")
https://cs.stackexchange.com/a/134600/123596
