全排列的生成算法就是对于给定的字符集，用有效的方法将所有可能的全排列无重复无遗漏地枚举出来。任何n个字符集的排列都可以与1～n的n个数字的排列一一对应，因此在此就以n个数字的排列为例说明排列的生成法。
n个字符的全体排列之间存在一个确定的线性顺序关系。所有的排列中除最后一个排列外，都有一个后继；除第一个排列外，都有一个前驱。每个排列的后继都可以从它的前驱经过最少的变化而得到，全排列的生成算法就是从第一个排列开始逐个生成所有的排列的方法。
全排列的生成法通常有以下几种：
字典序法
递增进位数制法
递减进位数制法
邻位交换法
n进位制法
递归类算法
本文介绍字典序法
字典序法中，对于数字1、2、3……n的排列，不同排列的先后关系是从左到右逐个比较对应的数字的先后来决定的。例如对于5个数字的排列 12354和12345，排列12345在前，排列12354在后。按照这样的规定，5个数字的所有的排列中最前面的是12345，最后面的是 54321。
一个全排列可看做一个字符串，字符串可有前缀、后缀。
生成给定全排列的下一个排列.所谓一个的下一个就是这一个与下一个之间没有其他的。这就要求这一个与下一个有尽可能长的共同前缀，也即变化限制在尽可能短的后缀上。
字典序算法如下：
一般而言，设P是[1,……,n]的一个全排列。
P=P1P2…Pn=P1P2…Pj-1PjPj+1……Pk-1PkPk+1……Pn
find: j=max{i|Pi<Pi+1}
k=max{i|Pi>Pj}
1，对换Pj，Pk，
2，将Pj+1……Pk-1PjPk+1……Pn翻转
P'= P1P2……Pj-1PkPn……Pk+1PjPk-1……Pj+1即P的下一个
【例】 如何得到346987521的下一个排列
1，从尾部往前找第一个P(i-1) < P(i)的位置
3 4 6 9 8 7 5 2 1
最终找到6是第一个变小的数字，记录下6的位置i-1
2，从i位置往后找到最后一个大于6的数
3 4 6 9 8 7 5 2 1
最终找到7的位置，记录位置为m
3，交换位置i-1和m的值
3 4 7 9 8 6 5 2 1
4，倒序i位置后的所有数据
3 4 7 1 2 5 6 8 9
则347125689为346987521的下一个排列
代码如下（C语言）：
// 版权所有（C）wu yudong
// 博客地址：http://www.wuyudong.com
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<ctype.h>
#include<stdlib.h>
#include<stdbool.h>
#include<time.h>
#define N 7
//int a[10]={1,0,2,3,4,5,6,7,8,9};
int a[N] = { 0, 1, 2, 3, 4, 5, 6 };
//交换list[a],list[b]
void Swap(int list[], int a, int b)
{
int temp = 0;
temp = list[a];
list[a] = list[b];
list[b] = temp;
return;
}
//将list区间[a,n]之间的数据由小到大排序
void Sort(int list[], int a, int n)
{
int temp = 0;
for (int i = 1; i < n - a; ++i) {
for (int j = a + 1; j < n - 1; ++j) {
if (list[j] > list[j + 1]) {
temp = list[j];
list[j] = list[j + 1];
list[j + 1] = temp;
}
}
}
return;
}
//全排列
void Prim(int list[], int n)
{
int num = 1, a = 0, b = 0;
for (int i = n; i > 0; --i) //计算有多少种情况，就循环多少次
num *= i;
while (num--) {
for (int i = 0; i < n; ++i) { //打印情况
printf("%d ", list[i]);
}
printf("\n");
for (int i = n - 1; i > 0; --i) {//从右往左，找出第一个左边小于右边的数，设为list[a]
if (list[i - 1] < list[i]) {
a = i - 1;
break;
}
}
for (int j = n - 1; j > a; --j) {//从右往左，找出第一个大于list[a]的数，设为list[b]
if (list[j] > list[a]) {
b = j;
break;
}
}
Swap(list, a, b); //交换list[a],list[b]
Sort(list, a, n); //将list[a]后面的数据，由小往大排列
}
return;
}
int main()
{
int begintime, endtime;
begintime = clock(); //计时开始
Prim(a,N);
endtime = clock(); //计时结束
printf("Running Time: %dms\n", endtime - begintime);
return 0;
}
Running Time: 2211ms
当然，这其中使用的排序算法还可以使用C语言中的qsort函数替代。但是因为数据量不大，所以运行时间相差不大
Comments