【全排列代码】这可能是全网最详细的解析了

全排列的定义

wiki百科的定义是：从n个元素中取出m个元素进行排列，当n=m时这个排列被称为全排列。

字典序、邻位对换法、循环左移法、循环右移法、递增进位制法、递减进位制法都是常见的全排列生成算法。

全排列的实现基本思想

字典序

科普：字典序，就是将元素按照字典的顺序（a-z, 1-9）进行排列。以字典的顺序作为比较的依据，可以比较出两个串的大小。一般的比较规则为基于ASCII码下。
以字典序法生成全排列生成全排列“123456789”，就是依次生成“123456789”->“123456798”->…->“987654312”->"987654321"这样的串。字典序法要求这一个与下一个有尽可能长的共同前缀，也即变化限制在尽可能短的后缀上。

【陈卫东, 鲍苏苏. 排序算法与全排列生成算法研究[J]. 现代计算机: 下半月版, 2007 (8): 4-7.】

算法步骤

具体代码

#include<iostream>
using namespace std;
	// P必须是从小到大排好序的
bool dictSeq(int P[],int length) {
    int j = -1;// 从最右端开始第一个比右边小的位置（逆序） 
    for (int i=length-2; i>=0; i--) {
        if (P[i] < P[i+1]) {
        	j = i;
            break;
        }
    }
    // j=-1此时已经是最大序了(最大序特点是：从右到左，每一个数字和它邻近右侧的数字不会产生规则下（规则指从大到小和从小到大）的逆序)
    if (j == -1) {
        printf("end");
        return false;
    }
    //j后边比j位置大的最小的一个位置Pk。 
    int k = -1;
    int min = 0x7fffffff;//假设Pk位置上的最小值为最大的int，方便后续的维护。 
    for (int i=j; i<length; i++) {
        if (P[i] > P[j] && P[i] <= min) { // 这里要找到最后一个，否则对于存在相同元素的集合会出现错误。
            min = P[i];							//如：0122 如果没有找到最后一个，那么j=1,k=2 后续Pk,Pj交换 为0212  
            k = i;									//再翻转后得到 0221 0221 本来的结果是0212，明显0221比0212字典序大，出现了混乱 
        }
    }
    // 交换Pj和Pk的值
    int tmp = P[j];
    P[j] = P[k];
    P[k] = tmp;
    // 对j后边的序列进行反转
	int left = j+1;
    int right = length - 1;
    while (left < right) {//翻转办法：从两头开始交换值 
    	int t = P[left];
        P[left] = P[right];
        P[right] = t;
        left ++;
        right --;
    }
    for (int i=0;i<length;i++) {
        printf("%d ",P[i]);
    }
    printf("\n");
    //产生比原序列字典序高一个等级的序列，并又放到了P数组中，一次结束 
    return true;
}
int main(){
	int a[]={4,6,8};
	//字典序最低的序列 
	for (int i=0;i<3;i++) {
        printf("%d ",a[i]);
    }
    printf("\n");
    //其余序列 
	for(int i=0;i<6;i++){ //n!次循环 
		dictSeq(a,3);
	}
	return 0;
}
/*输出样例*
4 6 8
4 8 6
6 4 8
6 8 4
8 4 6
8 6 4
end
*/ 

以字典序生成的全排列代码较为简单，看不懂就熟悉定义吧，具体的代码我在注释上已经很详细了。

邻位对换法

该算法由Johnson-Trotter首先提出，是一个能快速生成全排列的算法。它的下一个全排列总是上一个全排列对换某相邻两位得到的
算法步骤
具体代码

#include <iostream>
using namespace std;
enum DIR{LEFT=-1,RIGHT=1};
/*	函数功能：判断下标i所指pi元素是否处于活动状态
 *	输入参数：p	in,指向n个数字的一个当前排列
 *			dir	in,标记p中每个元素的箭头方向
 *			i	in,待判定元素的下标
 *			N	in,待排列字符的个数
 *	返回值：	true 表示待判定元素为活动状态，
 *				false 表示待判定元素处于非活动状态
 */
bool IsActive(const char *p,const DIR *dir,const int i,const int N)
{
	if(i+dir[i] < 0 || i+dir[i] >= N)//头或者尾的时候一定不是活跃状态 
		return false;
	if(p[i+dir[i]] < p[i])	//箭头所指一侧相邻的数比该数小
		return true;
	else 
		return false;
}
/*	函数功能：找到p中处于活动状态的数中的最大者
 *	输入参数：p	in,指向n个数字的一个当前排列
 *			dir in,标记p中每个元素的箭头方向
 *			N	in,待排列字符的个数
 *	返回值：上述最大者的下标，-1表示调用参数有误,N表示没有活动者
 */
int MaxActive(const char *p,const DIR *dir,const int N)
{
	int k=N;
	for(int i=0;i<N;i++)
		if(IsActive(p,dir,i,N) && (p[i] > p[k]))//如果有重复的话找到最后一个最大值 
			k = i;
	return k;
}
/*	函数功能：交换下标i所指元素与其箭头方向所指元素,原位交换
 *	输入参数：p	inout,指向n个数字的一个当前排列
 *			dir inout,标记p中每个元素的箭头方向
 *			i	in,待交换元素的下标
 *	返回值：	true 表示交换成功
 *			false 表示交换失败，失败原因为调用参数有误。
 */
bool Swap(char *p, DIR *dir, int *i)
{
	if(p == NULL || dir == NULL)
		return false;
	//交换相邻且是箭头指向的元素；
	char temp = p[*i];
	p[*i] = p[*i+dir[*i]];
	p[*i+dir[*i]] = temp;
	//元素对应的箭头（也即是对应下标-1和1的交换）交换
	DIR T = dir[*i];
	dir[*i] = dir[*i+T];
	dir[*i+T] = T;
 
	*i = *i + T;	//使*i依旧是未交换前*i所指元素的下标，这也是为什么要用指针传值的原因 
	return true;
}

/*	函数功能：上述算法思路第三步，修改所以比k大的元素的箭头方向，原位修改
 *	输入参数：p	in,指向n个数字的一个当前排列
 *			dir	inout,标记p中每个元素的箭头方向
 *			k	in,p中处于活动状态的最大者的下标，由MaxActive函数求出
 *			N	in,缓冲区p的长度,也是待排列字符的个数
 *	返回值：	true 表示函数执行成功
 *			false 表示函数执行失败，失败原因为调用参数有误
 */
bool ModifyDir(const char *p,DIR *dir,const int k,const int N)
{
	if(p == NULL || dir == NULL)
		return false;
	for(int i=0;i<N;i++){
		if(p[i]>p[k]){
			if(dir[i]==-1)
				dir[i]=RIGHT;
			else
				dir[i]=LEFT;
		}
	}
	return true;
}
int main()
{
	int N =0;
	cin>>N;
	char p[N+1] ;//多一个放'\0' 
	DIR dir[N] ;
	for(int i=0;i<N;i++)
	{
		p[i] = '1'+i;
		dir[i] = LEFT;
	}
	p[N]='\0';
	int k=0;
	cout<<p<<endl;
	while(1){
		k = MaxActive(p,dir,N);// 求所有处于活动状态的数中的最大者，设下标为k
		if(k == N)			//排列p＝（p1p2…pn）中无一数处于活动状态，则停止
			break;			
		Swap(p,dir,&k);		//	k和它的箭头所指的一侧的相邻数互换位置,此时对应指向的箭头也改变 
		ModifyDir(p,dir,k,N);//令比Pk大的所有数的箭头改变方向
		cout<<p<<endl;
	}
	return 0;
}
/*n==4输出样例*
	1234
	1243
	1423
	4123
	4变为不活跃状态 
	3变为活跃状态<- 
	4132
	3变为活跃状态<- 
	4又变为活跃状态 
	1432
	1342
	4变为不活跃状态 
	3变为活跃状态<- 
	1324
	3124
	3变为不活跃状态
	4变为活跃状态  <- 
	3142
	3412
	4312
	3变为活跃状态 <-
	4变为不活跃状态
	4321
	3421
	3变为不活跃状态 
	4变为活跃状态-> 
	3241
	3214
	4变为不活跃状态 
	1变为活跃状态-> 
	2314
	2变为不活跃状态 
	4变为活跃状态 <-
	2341
	2431
	4变为不活跃状态 
	3变为活跃状态 <-
	4231
	3变为不活跃状态 
	1变为活跃状态 <-
	4213
	2413
	1变为不活跃状态
	4变为活跃状态 -> 
	2143
	2134
*/

其他算法

由于方案太多，故其余生成方法只做简单的叙述，可以直接略过这部分了。

插入法

如果已知n-1个元素的排列，将n插入到排列的不同位置，就得到了n个元素的排列。用这种方法可以产生出任意n个元素的排列。这个方法有一个缺点：为了产生n个元素的排列，我们必须知道并存储所有n-1个元素的排列，然后才能产生出所有n阶排列。这个可以尝试用递归来解决。

杜瑞卿, 刘广亮. 整数分拆以及等差数列多重约束条件下全排列的生成法[J]. 2013.

递增进位制法

这个算法是基于序列的递增进位制数。递增进位制数是指数字的进制随着位数的递增而递增。一般情况下，数字最右边的进制是2，次右边的进制是3，以此类推。n位递增进位制数一共包含n!个数字，所以它可以与全排列生成算法结合在一起。

杜瑞卿, 刘广亮. 整数分拆以及等差数列多重约束条件下全排列的生成法[J]. 2013.

递减进位制法

该方法与递增进位制法的原理相似，不同的是它定义的“递减进位制数”是数字的进制随着位数的递增而递减。这种进制一般最左边的进制是2，次左边的进制是3。其余原理与递增进位制法基本相同。

杜瑞卿, 刘广亮. 整数分拆以及等差数列多重约束条件下全排列的生成法[J]. 2013.

循环左移法

循环左移全排列生成算法是全排列生成算法的一种，与递减进位全排列生成算法非常相似。所谓左循环搜索法是指从起始数字开始向左搜索，如果到了左边界还没有发现终止数字，则从右边界开始继续寻找，直到终止数字被发现。该算法的总算数复杂度为O(nnn!)。

百度百科 《循环左移全排列生成算法》

循环右移法

类似左移

网上广为流传的递归代码解释

具体代码

#include <iostream>
#include <cstdio>
using namespace std;
 
void permutation(int k, int n, int a[])
{
    //递归到底层
    if(k == n-1)
    {
        for(int i = 0; i < n; i ++)
            printf("%d", a[i]);
        printf("\n");
    }
    else
    {
        for(int i = k; i < n; i ++)
        {
            swap(a[k],a[i]);
            //交换后递归下一层
            permutation(k+1, n, a);
            //保证每一层递归后保持上一层的顺序
            swap(a[k],a[i]);
        }
    }
}
int main()
{
    int a[100];
    int n;
    scanf("%d", &n);
 
    for(int i = 0; i < n; i ++)
        a[i] = i+1;
 
    permutation(0, n, a);
    return 0;
}

这个代码可以这样构建：首先函数部分先不要看递归 ，if部分也就是输出整个序列，直接到else部分，我们规定【k的含义为第k层】那么，k如果为第一层也就是0时，第一个数字分别与每一个数字交换。以此类推……

void permutation(int k, int n, int a[])
{
    //递归到底层
    if(k == n-1)
    {
        for(int i = 0; i < n; i ++)
            printf("%d", a[i]);
        printf("\n");
    }
    else
    {
        for(int i = k; i < n; i ++)
        {
            swap(a[k],a[i]);
        }
    }
}

看懂这一层之后，再完善代码：加上递归之后的代码是在每一层的基础之下进行访问下一层，直到最后一层，也就是k==n-1时，输出这个序列，注意（else的for循环中i=k是不可以改成i=k+1的！！！因为最后一层的上一层的序列也需要输出！）
递归完之后再将序列顺序保持到上一层的顺序，然后再进行递归。因为数组只有一个，而递归却有很多次。

void permutation(int k, int n, int a[])
{
    //递归到底层
    if(k == n-1)
    {
        for(int i = 0; i < n; i ++)
            printf("%d", a[i]);
        printf("\n");
    }
    else
    {
        for(int i = k; i < n; i ++)
        {
            swap(a[k],a[i]);
            //交换后递归下一层
            permutation(k+1, n, a);
            //保证每一层递归后保持上一层的顺序
            swap(a[k],a[i]);
        }
    }
}

提供一个具体样例供参考
4
1234
1243
1324
1342
1432
1423
2134
2143
2314
2341
2431
2413
3214
3241
3124
3142
3412
3421
4231
4213
4321
4312
4132
4123
那么我按层次的思想来看的话就是这样的(从上到下，从左到右)

层数	具体
first	1234 2134 3214 4231
second	1234 2134 3214 4231
second	1324 2314 3124 4321
second	1432 2431 3412 4132
third	1243 2143 3241 4231
third	1234 2134 3214 4213

具体到一个：
如第一层的1234 在第一层的时候分别与自身交换，所以不会改变自己的值 所以1234–》1234
递归进入第二层 第二个数和第二个数交换，第二个数和第三个数交换，第二个数和第四个数交换
所以1234–》1324–》1432
以第二层的每个数再次递归进入第三层 第三个数和第三个数交换 第三个数和第四个数交换
所以1243–》1234
其他数字也一样

可能会持续更新……