有序全排列生成算法
作者：goal00001111（高粱） 写本文的动力来自一个NOI题目：输出n个数的第m种全排列。
输入两个自然数m,n 1<=n<=20，1<=m<=n!
输出n个数的第m种全排列。
要解决这个问题，必须要生成有序的全排列。
生成n个
数字的全排列是算法学习中的一个经典案例，也是信息学奥赛中的一个常考内容，值得我们去深入研究。生成全排列的算法很多，大概分类有直接模拟法，设置中介
数法和数学分析法（这是我杜撰的一个名称），其中直接模拟法又可以分为递归和非递归模拟。设置中介数后，更是可以分为字典序全排列生成法，递增进位排列生
成算法，递减进位排列生成算法和循环左移排列生成算法等类别。此外还有邻位对换法和邻元素增值法等另类生成方法。利用这些算法生成的全排列，有些是有序全
排列，有些却是无序的，本文主要探讨有序全排列。
在上面列举的算法中，字典序全排列生成法和邻元素增值法，以及我杜撰的数学分析法可以生成有序全排列，即可以输出n个数的第m种全排列。其中字典序全排列
生成法根据是否设置中介数又可以分为两类，不用设置中介数的方法即直接模拟法。
我
们首先来看最简单的递归直接模拟法。这是普通递归方法的一个改进。普通的递归方法是利用将当前数组左界元素与其右侧的元素交换位置来实现排列，这样得到的
全排列是无序的。所以我们不能直接调换位置，而是将左界右侧的元素顺序右移，不破坏原排列的顺序，保证右侧元素的递增性。
为了回答本文开头提出的问题，我们统一设置一个接口void Permutation(long long n, long long
m);其中n表示共n个自然数，m表示第m种全排列。
在子程序中我们先创建一个数组a[n]来存储n个自然数，然后递归查找并输出n个数的第m种全排列。下面是主要的代码：（完整的代码附在文章后面，下同）
/*
函数名称：Permutation
函数功能：输出n个数的第m种全排列
输入变量：long long n：1，2，3，...，n共n个自然数（1<=n<=20） long long
m：第m种全排列（1<=m<=n!） 输出变量：无 */
void Permutation(long long n, long long m)// 递归直接模拟法
{ long long *a = new long long[n];//用来存储n个自然数 for (int i=0; i<
=m<=n!） long long & s：记录当前是第几个全排列 输出变量：找到第m种全排列返回true，否则返回false
*/
bool Try(long long a[], int left, int right, long long m, long long
& s)
{ if (left == right)//已经到达数组的右界，直接输出数组 { s++; if (s == m)//找到第m种全排列 {
cout << s << ": "; for (int i=0; i<=right; i++) { cout
<< a[i] << ' '; } cout << endl; return true; } } else
{ //将当前最左边的元素与其后面的元素交换位置 //当i=left时，与自身交换，相当于不换，直接输出 for (int i=left;
i<=right; i++) {//这是与其他递归算法所不同的地方，其他算法是Swap(a[left],a[i]);
MoveRight(a, left, i); if (Try(a, left+1, right, m,
s))//左界右移一位，递归寻找第m种全排列 { return true; } MoveLeft(a, left, i);//再换回来 } }
return false;
}
在递归函数Try中，我们每次只分析left与right之间的元素，并不断将left右移，当left==right时，一个全排列被生成。
在这里我们用void MoveRight(long long a[], int left, int right)代替普通递归算法中的void
Swap(long long a[], int left, int
right)；函数功能是将left与right之间的元素按顺序右移，而right位置的元素左移到left位置。这样可以保证left+1与
right之间的元素按增序排列。
我在这里先简单的介绍子函数MoveRigh和MoveLeft的功能，而把重点放在对主要功能函数Permutation和Try的理解上。函数的完整
代码我放在了文章后面，有兴趣的读者也可以自己实现。以下的内容也采用这种方法。
递归直接模拟法算法简单明了，当m较小的时候还是很实用的（与n的大小关系不大），我的测试结果是当n =
100，m=10000000时，用时为1秒；当n = 1000，m=10000000时，用时为2秒；当n =
10000，m=10000000时，用时为3秒。
比递归直接模拟法速度更快的是循环直接模拟法，用循环代替递归，可以大大的减小开销，提高速度。循环直接模拟法又叫字典序生成算法，以下有关字典序生成算
法的文字转载自网友visame的专栏。
字典序生成算法：
设P是1～n的一个全排列:p = p1p2...pn = p1p2...pj-1pjpj+1......pk-1pkpk+1...pn
1）从排列的右端开始，找出第一个比右边数字小的数字的序号j（j从左端开始计算），即j = max{i | pi < pi+1}
2）在pj的右边的数字中，找出所有比pj大的数中最小的数字pk，即 k = max{i | pi < pi+1}
（右边的数从右至左是递增的，因此k是所有大于pj的数字中序号最大者）
3）对换pj，pk
4）再将pj+1......pk-1pkpk+1...pn倒转得到排列p' =
p1p2...pj-1pjpn......pk+1pkpk-1...pj+1，
这就是排列p的下一个排列。
例如839647521是数字1～9的一个排列。从它生成下一个排列的步骤如下：
自右至左找出排列中第一个比右边数字小的数字4；
在该数字后的数字中找出比4大的数中最小的一个5；
将5与4交换得到839657421； 将7421倒转得到839651247；
所以839647521的下一个排列是839651247。
下面我们用c++代码来实现字典序生成算法，函数接口与递归直接模拟法完全一样。在子程序中我们先创建一个数组a[n]来存储n个自然数，然后使用循环直
接输出n个数的第m种全排列。下面是主要的代码：（完整的代码附在文章后面，下同）
void Permutation(long long n, long long m)
{ long long *a = new long long[n];//用来存储n个自然数 for (int i=0; i<< m << ": "; //输出n个数的第m种全排列
int left, right;
long long temp;
for (int i=1; i= 0 && a[left] > a[left+1])
left--;
right = n - 1;
while (a[right] < a[left])//找到左边界右边数组中比a[left]大的最小的元素，这个就是要取代a[left]的元素
right--;
temp = a[left]; a[left] = a[right]; a[right] = temp; //交换a[right]和a[left]
left++; //左边界增1，保证此时左右边界之间的元素是一个递减排列
right = n -1;
while (left < right)//逆置左右边界之间的元素，使其按增序排列
{
temp = a[left]; a[left] = a[right]; a[right] = temp;
left++;
right--;
}
}
for (int i=0; i<<
a[i] << " "; } cout << endl; delete []a;
}
与递归直接模拟法算法相比较，循环直接模拟法在m较大具有明显优势，我的测试结果是当n =
100，m=10000000时，递归直接模拟法用时为1秒，而循环直接模拟法用时为0秒；当n =
100，m=50000000时，递归直接模拟法用时为8秒，而循环直接模拟法用时为3秒。
接下来要讲的第三种算法是需要设置中介数的字典序全排列生成法，这是我从组合数学的教材中获得的一种方法。它通过生成初始排列的中介数和序数m的递增进位
制数，产生一个新的映射，再将映射还原，得到新的全排列。以下关于递增进位制和字典全排列生成法的映射和还原方法转载自speedfirst
的Blog。
递增进位制和递减进位制数：
所谓递增进位制和递减进位制数字是指数字的进制随着数字位置的不同递增或递减。通常我们见到的都是固定进制数字，如2进制，10进制等。m位n进制数可以
表示的数字是m*n个。而m位递增或递减进位制数则可以表示数字m!个。例如递增进位制数4121，它的进制从右向左依次是2、3、4、5。即其最高位
（就是数字4那位）最大值可能是4；第三高位最大可能是3；第二高位最大可能是2；最末位最大可能是1。如果将4121加上1的话，会使最末位得到0，同
时进位；第二位的2与进位相加，也会得到0，同时进位；第三位的1与进位相加得到2，不再进位。最终得到结果是4200。递减进位制的道理是一样的，只不
过进制从右向左依次是9、8、7、6……，正好与递增进位制相反。
接下来要了解的是递增进位制、递减进位制数和其序号的关系。递增、递减进位制数可以被看作一个有序的数字集合。如果规定递增进位制和递减进位制数的0的序
号是十进制0，递增进位制数的
987654321和递减进位制数的123456789对应十进制序号362880（即9!），则可以整理一套对应法则。其中，递增进位制数（a1
a2 a3 a4 a5 a6 a7 a8 a9）为：
a1*9! + a2*8! + ….+ a8*2! + a9*1! = 序号
例如序号100的递增进位制数就是4020，即4*4！+ 0*3！+ 2*2！+ 0*1！=
100。将一个序号转换成其递增进位制数首先需要找到一个比序号小的最大阶乘数（即1、2、6、24、120、720……），对其进行整数除得到递增进位
制的第一位；将除法的余数反复应用这个方法（当然，之后选择的余数是小一级的阶乘数），直到余数为0。
递减进位制数（a1 a2 a3 a4 a5 a6 a7 a8 a9）为：
(((((((((a1 * 1 + a2) * 2 + a3) * 3 + …… + a7) * 8 + a8) * 9 + a9 = 序号
例如序号100的递减进位制数就是131，即（1*8 + 3）*9 + 1 =
100。将一个序号转换成其递减进位制数，需要对序号用9取余数，就可以得到递减进位制的最末位（这点和递增进位制先算出最高位相反）。用序号整除9的商
作为新的序号重复此过程（当然，依次对8、7、6……取余求商），直到余数为0。
关于递增进位制和递减进位制需要注意的重点：一是其加减法的进位需要小心；二是序号和数字的转换。除了100之外，常见的转换有：999的递增数是
121211，递减数是1670；99的递增数是4011，递减数是130。
上面的一段文字是我从网友speedfirst的博客中转载而来的，而关于已知序号求递增进位制数和递减进位制数，以及求字典序全排列生成算法的映射方法
等功能函数，我已经用c++语言实现了，并附在本文的末尾，有兴趣的读者可以参考一下。
接下来我们看字典序全排列生成算法的映射和还原方法。
映射方法：将原排列数字从左到右（最末尾不用理会），依次查看数字右侧比其小的数字有几个，个数就是中介数的一位。例如，对于排列839647521。最
高位8右侧比8小的有7个数字，次高位3右侧比3小的数字有2个，再次位的9的右侧比9小的有6个数字，……，2的右侧比2小的数有1个。得到递增进制中
介数 72642321。（此中介数加上100的递增进位制数4020后得到新中介数72652011）。
还原方法：还原方法为映射方法的逆过程。你可以先写出辅助数字1 2 3 4 5 6 7 8
9，以及9个空位用于填充新排列。然后从新中介数的最高位数起。例如新中介数最高位是x，你就可以从辅助数字的第一个没有被使用的数字开始数起，数到x。
第x+1个数字就应当是空位的第一个数字。我们将此数字标为“已用”，然后用其填充左起第一个空位。然后，再看新中介数的次高位y，从辅助数字的第一个未
用数字数起，数到1。第y+1个数字就是下一个空位的数字。我们将此数字标为“已用”，然后用其填充左起第二个空位。依此类推，直到最后一个中介数中的数
字被数完为止。例如对于新中介数72652011，我们给出其辅助数字和空位的每一步的情况。其中红色的数字代表“正在标记为已用”，“已用”的数字不会
再被算在之后的计数当中。当新中介数中所有的数字都被数完了，辅助数字中剩下的唯一数字将被填入最后的空位中。最终得到新排列839741562。
新中介数当前位 辅助数字 新排列数
初始 1 2 3 4 5 6 7 8 9 7 1 2 3 4 5 6 7 8 9 8 2 1 2 3 4 5 6 7 8 9 8 3 6 1
2 3 4 5 6 7 8 9 8 3 9 5 1 2 3 4 5 6 7 8 9 8 3 9 7 2 1 2 3 4 5 6 7 8 9 8
3 9 7 4 0 1 2 3 4 5 6 7 8 9 8 3 9 7 4 1 1 1 2 3 4 5 6 7 8 9 8 3 9 7 4 1
5 1 1 2 3 4 5 6 7 8 9 8 3 9 7 4 1 5 6 最后补位 8 3 9 7 4 1 5 6 2
要想得到n个数字的第m个全排列，我们只需要设初始全排列为123456789，序数为（m-1），通过映射和还原后就可以得到第m个全排列了。主要功能
函数的c++代码如下：
void Permutation(long long n, long long m)
{ int *a = new int[n];//用来存储n个自然数，也可以看成是初始全排列1234...n for (int i=0; i<< m << ": "; //输出n个数的第m种全排列
int *diZ = new int[n-1]; //用来存储序号m的递增进位制数，设所有元素的初值为0
for (int i=0; i< zhongJie[i])
{
if (a[j] != -1)
s++;
j++;
}
while (a[j] == -1)
j++;
b[i] = a[j];
a[j] = -1; //用-1表示该位置已经被填充
}
for (int i=0; i<<
b[i] << ' '; } cout << endl; delete []a; delete []b; delete
[]p; delete []diZ; delete []zhongJie;
}
设置了中介数的字典序全排列生成算法，与递归直接模拟法和循环直接模拟法的最大不同是，不需要模拟有序全排列的生成过程，也就不需要逐一地生成各个全排
列，只要知道初始全排列，就能根据序号（m-1），直接得到第m个全排列，因此速度非常快。它的缺点是在生成序号（m-1）的递增进进制数时，需要事先创
建一个用来存储n的阶乘数n!
的数组p[]，所以n的值不能太大，否则就会溢出，根据我的测试结果，当1<=n<=20时不会溢出，当21<=n时会溢出。
测试比较：当n = 20，m=10000000时，递归直接模拟法用时为1秒，循环直接模拟法用时为0秒，而字典序全排列生成算法用时为0秒；当n
= 20，m=50000000时，递归直接模拟法用时为8秒，循环直接模拟法用时为3秒，而字典序全排列生成算法用时为0秒；
当n =
20，m=500000000时，递归直接模拟法用时超过80秒，循环直接模拟法用时为50秒，而字典序全排列生成算法用时为0秒；实际上，对于long
long范围内的任意自然数，字典序全排列生成算法用时都是0秒。
接
下来介绍一个我原创的东西，我称之为数学分析法，因为它的发现是对各个全排列的数学规律进行分析后得到的。这个算法是我在做本文开头的题目时自己想出来
的，后来去网上搜索时也没有发现类似算法。其实我的算法和字典序全排列生成算法思路有点相同，只不过我没有设置中介数而已。后来听说有一个叫什么康托展开
的东西，它是已知某个有序全排列，可以求出它的序号，跟本文谈论的话题刚好相反，但是使用逆向思维的方法，可以从中得到启发——关于康托展开的实现代码我
也在文章末尾给出了。
我的算法也许和康托展开有一定关系——我不知道，因为我也是事后才知道有康托展开一说的——大家可以去寻找一下两者的联系。
算法思路是利用n个数字的全排列总量是n!个的原理，如果m小于i！，则前n-i个元素无需移动位置，这样相当于求i个数字的第m个全排列，范围缩小了。
再使用迭代的方法，不断的减小m的值，缩小全排列的范围，直到能够直接写出全排列。这一点和求递增进位制数的算法很相似，
具体的操作是用一个数组顺序存储n个数字，数组初始化为顺序排列的n个数字，即a[n]={1,2,...,n-1}
；再用一个数组顺序存储n个数字的全排列数量,即n!，得到p[n]={1,2,6,...,n!} 。
选择点一：如果m=1，则直接输出数组a[n]；
选择点二：如果m=2，则调换a[n-1]与a[n-2]，再输出数组a[n]；
选择点三：若m>2，查找p[r-1] < m <= p[r]，设左界left = n-r+1；
选择点四：若m = p[r]，从a[0]~a[left-1]的元素原样输出，从left开始到最后的元素逆序输出；
选择点五：若m < p[r]， 设s = m/p[r-1]，y = m%p[r-1]；
选择点六：若y = 0，则从a[0]~a[left-1]的元素原样输出，a[left]=a[left+s-1]；left之后的元素逆序输出；
选择点七：若y != 0，则从a[0]~a[left-1]的元素原样输出，a[left]=a[left+s]，m = y；
转化为求left之后的元素的第m（此时m也已经变小）个全排列。
C++代码实现主要功能函数如下：
void Permutation(long long n, long long m)
{ long long *a = new long long[n];//用来存储n个自然数 for (int i=0; i<< m << ": "; //输出n个数的第m种全排列
while (m > 1)//通过判断m的值排列数组a的元素
{
//若m=1，什么也不做，直接输出数组
if (m == 2) //若只要求输出第2个排列，直接交换数组最后两个元素
{
long long temp = a[n-1];
a[n-1] = a[n-2];
a[n-2] = temp;
break; //跳出循环
}
else if (m > 2)
{
int pos = Compare(p, n, m);//查找pos，使得p[pos-1] < m <= p[pos]
int left = n - 1 - pos;//由于m <= p[pos]，所以前n-1-pos个元素不必移动，故让数组的左界移至n-1-pos位
if (p[pos] == m)//如果p[pos] == m，直接逆置以left为左界的数组
{
Reverse(a, left, n-1);//逆置数组[left, n-1)]区间的元素
break; //跳出循环
}
else
{
int r = m / p[pos-1] + left;//计算将要置放在left位的元素位置
m %= p[pos-1]; //改变m的值----这是本算法的关键！
if (m == 0)//如果m是p[pos-1]的倍数，将第r-1位元素移动到left位
{
Move(a, left, r-1);
Reverse(a, left+1, n-1); //逆置数组[left+1, n-1)]区间的元素
}
else//否则将第r位元素移动到left位，并根据新的m值计算全排列 {
Move(a, left, r);
}
}
}
}
for (int i=0; i<<
a[i] << " "; } cout << endl; delete []a; delete []p;
} 这里同样需要事先创建一个用来存储n的阶乘数n! 的数组p[]，所以n的值不能太大。使用了三个子函数int Compare(long
long p[], int n, long long m)，void Reverse(long long a[], int left, int
right)和void Move(long long a[], int left, int pos)，实现的功能分别为：
Compare用来寻找使得p[pos-1] < m <=
p[pos]的数组下标pos，确保m<=p[n-1]，返回满足条件的数组下标pos；Reverse用来逆置数组的左界left和右界
right直接的元素；Move负责将pos位的元素向左移动到left位，而left~（pos-1）位的元素则依次右移一位，功能其实和递归直接模拟
法中用到的MoveRight一模一样。和前面的子函数一样，完整代码放在了文章末尾的附录中。
我的数学分析法的速度几乎和字典序全排列生成算法一样快，当n =
20，m=500000000时，用时为0秒。由于不需要构造中介数，所以我认为数学分析法比字典序全排列生成算法容易理解——只需要一点点排列组合的知
识和一点点逻辑推理能力，呵呵！
最后再给大家介绍一种比较另类的方法：邻元素增值法（n进制法）。算法思路如下：
1）从原始排列p =
p1p2......pn开始，第n位加n-1，如果该位的值超过n，则将它除以n，用余数取代该位，并进位（将第n-1位加1），执行2）；若没有进位
则产生一个新的排列，跳过2），3），直接执行4）；
2）若第n位产生了进位，将第n-1位加1。若第n-1位的值超过n，则将它除以n，用余数取代该位，并进位；
3）按同样方法处理n-2位，n-1位，......，直至不再发生进位为止，处理完一个排列，产生一个新的排列；
4）若新全排列中有相同元素，则表示该全排列错误，不能记录到全排列总数中；
5）当第一个元素的值大于n时，所有全排列都已经产生，程序结束。
以3个数1，2，3的全排列为例：
原始排列是1 2 3，从它开始，第3个元素是3，3 + 2 = 5 > 3，有进位，5 mod 3 = 2；第2个元素是2，2+1 =
3，没有进位，所以新排列是1 3 2。
由于此时第一个元素的值1不大于3，继续对排列1 3 2进行邻元素增值操作：第3个元素是2，2 + 2 = 4 > 3，有进位，4 mod
3 =1；第2个元素是3，3+1 = 4 > 3，有进位，4 mod 3 =1；第1个元素是1，1+1 = 2，没有进位，所以新排列是2
1 1。
继续对排列2 1 1进行邻元素增值操作，得到新排列2 1 3。
依此类推，直到第一个元素的值大于3，我们可以得到所有的全排列（包括错误的排列）。
顺序产生的排列是：1 2 3，1 3 2，2 1 1，2 1 3，2 2 2，2 3 1，2 3 3，3 1 2，3 2 1
有的排列中存在重复元素（如2 1 1和2 2 2等），丢弃，余下的就是所有正确的全排列，而且我们可以发现，这些全排列是有序的。
C++代码实现如下：
void Permutation(long long n, long long m)
{ long long *a = new long long[n];//用来存储n个自然数 for (int i=0; i<< m << " : ";
long long s = 1;
int pos;
while (s < m)
{
pos = n - 1; //最后一位加n-1
a[pos] = (a[pos] + pos);
while (a[pos] > n)//若有进位，前一元素加1，直到没有进位为止
{
a[pos--] -= n;//大于n则取余数，实际上a[pos]一定比2*n小
a[pos] += 1; //前一元素加1
}
if (a[0] > n)//当第一个元素的值>n则结束
break;
if (IsRight(a, n))//若数组a中不存在重复元素，说明得到了一个正确的全排列
{
s++;
}
}
for (int i=0; i<<
a[i]; cout << endl; delete []a;
}
其中用到了一个子函数bool IsRight(long long a[], int
n)，作用是判断当前全排列是否正确，即数组a中是否存在重复元素，若存在重复元素则返回false，否则返回true。
此种算法实现起来非常简单，是上述所有算法中代码最短的一个，但是由于每得到一个新的全排列，都要遍历数组a[]判断是否有重复元素，增大了计算量，大大
减缓了速度，所以成了速度最慢的一个。我们拿它和模拟法算法进行比较。
当n = 10，m=10000时，三种算法用时均为0秒；当n =
10，m=100000时，递归直接模拟法用时为0秒，循环直接模拟法用时为0秒，而邻元素增值法用时为5秒；当n =
10，m=200000时，递归直接模拟法用时为0秒，循环直接模拟法用时为0秒，而邻元素增值法用时为10秒。
到这里，我就把我目前所知的五种有序全排列的生成算法都向大家做了介绍，它们或直截了当，或曲径通幽，或代码简短，或速度迅捷。所谓“萝卜白菜，各有所
爱”，希望阅读了全文的读者们都能有所收获。
另外，如果大家不觉得读我的文章是浪费时间，并且意犹未尽的话，我打算将其他的几种非有序排列算法在下一篇文章中向大家介绍，这些算法虽然不能生成有序全
排列，但是速度非常快，非常值得一看。 参考文献：
1.《组合数学——排列数生成算法详解》speedfirst 的Blog
http://www.newsmth.net/pc/pcdoc.php?userid=speedfirst&pid=0&tag=0&order=&tid=18452
2.《全排列的生成算法》 visame的专栏
http://blog.csdn.net/visame/archive/2008/05/18/2455396.aspx
附录：
《康托展开》：http://blog.csdn.net/goal00001111/archive/2008/11/18/3326662.aspx
《递增进位制和递减进位制数》：
http://blog.csdn.net/goal00001111/archive/2008/11/18/3326765.aspx
《有序全排列生成算法集锦》
http://blog.csdn.net/goal00001111/archive/2008/11/18/3326642.aspx
评论