# # Permutation generation algorithm

In the work, we need to simulate and analysis all kinds of permutation condition on the computer.
So let me tell you some methods to generate permutation.

## # 1.The ordinal method produces permutations

Let a permutation $P_1,P_2,\ldots,P_n$ correspond to sequence $(a_{n-1},a_{n-2},\ldots,a_2,a_1)$ ,Let it increment from the initial value, corresponding to all permutations.

#### # Prove that bijection

If we want to get a sequence $(a_{n-1},a_{n-2},\ldots,a_2,a_1)$ to express all permutation, we need to prove that we can structure a sequence satisfied bijection.

let me prove it:

$n!=n(n-1)!=[(n-1)+1](n-1)!=(n-1)(n-1)!+(n-1)!$

Similay: $(n-1)!=(n-2)(n-2)!+(n-2)!$

So, let's substitute that in the $n!$ :
$n!=(n-1)(n-1)!+(n-2)(n-2)!+(n-2)!$
$=(n-1)(n-1)!+(n-2)(n-2)!+(n-3)(n-3)!+\ldots+2\times2!+2!$
$=\sum_{k=1}^{n-1} k \times k!+1$

So,

$n!-1=(n-1)(n-1)!+(n-2)(n-2)!+(n-3)(n-3)!+\ldots+2\times2!+1\times1!$

So, we define a integer $m$ that $m \in$ $\{$ $x$ $|$ $0 \leq$ $x$ $\leq$ $n!-1$ , $x \in Z$ $\}$
and m can be uniquely represented as(m is the number of each permutation):

$m=a_{n-1}(n-1)!+a_{n-2}(n-2)!+\ldots+a_2\times2!+a_1$

$a_k$ satisfied that $0 \leq a_k \leq k,k=1,2,\ldots,n-1$.

So,we can prove that sequence and permutation correspond one to one.

#### # Method of getting sequence using m

When gave us a m ($0 \leq m \leq n!-1$), how do we find the permutation that m represents it.

Let us divide $m$ by 2. And reminder is $r_1$ , then $r_1=a_1$:

$m=a_{n-1}(n-1)!+a_{n-2}(n-2)!+\ldots+a_2\times2!+a_1$

$n_1=m$

$n_2=\lfloor{ \frac{n_1}{2} }\rfloor =a_{n-1} \frac{(n-1)!}{2!}+a_{n-2} \frac{(n-2)!}{2!}+\ldots+a_2,r_1=a_1$

Similary:

$n_3=\lfloor{ \frac{n_1}{3} }\rfloor =a_{n-1} \frac{(n-1)!}{3!}+a_{n-2} \frac{(n-2)!}{3!}+\ldots+a_3,r_2=a_2$

So:

$n_{i+1}=\lfloor{ \frac{n_i}{i+1} }\rfloor ,r_i=a_i,i=1,2,\ldots,n-1$

So we iterate and we figure out the sequence:$(a_{n-1},a_{n-2},\ldots,a_2,a_1)$

#### # Method of getting sequence using permutation

And how can we get the m through the sequence? We have given the method in the proof.
but I will give a new method to get m:
I define the permutation of n number to be $P_1,P_2,\ldots,P_n$ and its sequence is $(a_{n-1},a_{n-2},\ldots,a_2,a_1)$.
Now if I can get the sequence I can get the m; I will give the method:
$a_i$ = the number of Numbers on the right-hand side of $i+1$ that are smaller than $i+1$.
So,we can get m by the proof in the last page.

#### # Method of getting permutation using sequence

how can we get the permutation, the method is the inverse process of the above method.

## # 2.Lexicographical ordering generates permutations

Lexicographical ordering generates permutations is the simplest and most commonly used method.
In this method, we ranked the permutations by its Lexicographical ordering.
For example, we permutate the 1,2,3,4. the smallest number of the permutations is 1234, the biggest number of the permutations is 4321.