# 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 P1,P2,,PnP_1,P_2,\ldots,P_n correspond to sequence (an1,an2,,a2,a1)(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 (an1,an2,,a2,a1)(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(n1)!=[(n1)+1](n1)!=(n1)(n1)!+(n1)!n!=n(n-1)!=[(n-1)+1](n-1)!=(n-1)(n-1)!+(n-1)!

Similay: (n1)!=(n2)(n2)!+(n2)!(n-1)!=(n-2)(n-2)!+(n-2)!

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

So,

n!1=(n1)(n1)!+(n2)(n2)!+(n3)(n3)!++2×2!+1×1!n!-1=(n-1)(n-1)!+(n-2)(n-2)!+(n-3)(n-3)!+\ldots+2\times2!+1\times1!

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

m=an1(n1)!+an2(n2)!++a2×2!+a1m=a_{n-1}(n-1)!+a_{n-2}(n-2)!+\ldots+a_2\times2!+a_1

aka_k satisfied that 0akk,k=1,2,,n10 \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 (0mn!10 \leq m \leq n!-1), how do we find the permutation that m represents it.

Let us divide mm by 2. And reminder is r1r_1 , then r1=a1r_1=a_1:

m=an1(n1)!+an2(n2)!++a2×2!+a1m=a_{n-1}(n-1)!+a_{n-2}(n-2)!+\ldots+a_2\times2!+a_1

n1=mn_1=m

n2=n12=an1(n1)!2!+an2(n2)!2!++a2,r1=a1n_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:

n3=n13=an1(n1)!3!+an2(n2)!3!++a3,r2=a2n_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:

ni+1=nii+1,ri=ai,i=1,2,,n1n_{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:(an1,an2,,a2,a1)(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 P1,P2,,PnP_1,P_2,\ldots,P_n and its sequence is (an1,an2,,a2,a1)(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:
aia_i = the number of Numbers on the right-hand side of i+1i+1 that are smaller than i+1i+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.

# Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include<cstdio>
#include<iostream>
using namespace std;
int get_index_P(int b[],int n)
{
int *a;
int m=0;
a = new int[n+1];
for(int i=1;i<=n-1;++i)
{
int tmp;
for(int j=1;j<=n;j++)
{
if(b[j]==i+1)
{
tmp=j;
}
}
int num=0;
for(int j=tmp;j<=n;j++)
{
if(b[tmp]>b[j])
{
num++;
}
}
a[i]=num;
}
for(int i=n-1;i>=1;i--)
{
cout<<a[i]<<" ";
}
cout<<endl;
int factorial=1;
for(int i=1;i<=n-1;++i)
{
factorial*=i;
m+=(factorial*a[i]);
}
delete[] a;
return m;
}
void get_a_P(int m,int n)
{
int *a;
a = new int[n+1];
int factorial=1;
for(int i=2;i<=n;i++)
{
a[i-1]=m%i;
m/=i;
}
for(int i=n-1;i>=1;i--)
{
cout<<a[i]<<" ";
}
cout<<endl;
}
int main()
{
int n;
int *P;

cout<<"请输入排列长度n"<<endl;
cin>>n;

P=new int[n+1];

cout<<"请输入一组以n为长度的排列"<<endl;
for(int i=1;i<=n;++i)
{
cin>>P[i];
}
cout<<"输入排列找到对应的序列和序数"<<endl;
int m = get_index_P(P,n);
cout<<"这是该排列的序数"<<m<<endl;
cout<<"输入序数求对应的序列"<<endl;
get_a_P(4000,7);
delete[] P;
return 0;
}

# 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.

# Method of getting m and sequence

# Method of permutation generation

# Method of getting next permutation