「全排列算法」全排列算法

全排列算法

一、递归法

引用：https://www.cnblogs.com/mengfanrong/p/3854044.html

比如，假设集合是{a,b,c},那么这个集合中元素的全部排列是{(a,b,c),(a,c,b),(b,a,c),(b,c,a),(c,a,b),(c,b,a)}，显然，给定n个元素共同拥有n!种不同的排列，假设给定集合是{a,b,c,d}，能够用以下给出的简单算法产生其全部排列，即集合(a,b,c,d)的全部排列有以下的排列组成：

（1）以a开头后面跟着(b,c,d)的排列

   （2）以b开头后面跟着(a,c,d)的排列

   （3）以c开头后面跟着(a,b,d)的排列

   （4）以d开头后面跟着(a,b,c)的排列，这显然是一种递归的思路，于是我们得到了下面的实现：

#include<iOStream>
#include<string>
using namespace std;

re_comb(string a,int k,int len)//k表示当前递归第一个数的位置 
{
	int i;
	if(k==len)//当k=len时，输出；即，每一位都已经确定。 
	{         //然后退出一层，接着for循环，再输出 
		cout<<a<<endl;
	} 
	else
	{
		for(i=k;i<len;i++)
		{
			swap(a[i],a[k]);
			re_comb(a,k+1,len);//将k位置之后的元素进行全排列。 
			swap(a[i],a[k]);//恢复 
		}
	}
} 

int main()
{
	string a;
	getline(cin,a);
	re_comb(a,0,a.length());
	return 0;
}

先定下第i位，然后将第i位之后的数全排列。

二、字典序法

引用：https://blog.csdn.net/cpfeed/article/details/7376132

算法定义

首先看什么叫字典序，顾名思义就是按照字典的顺序（a-z, 1-9）。以字典序为基础，我们可以得出任意两个数字串的大小。比如 "1" < "12"<"13"。就是按每个数字位逐个比较的结果。对于一个数字串，“123456789”，可以知道最小的串是从小到大的有序串“123456789”，而最大的串是从大到小的有序串“*987654321”。这样对于“123456789”的所有排列，将他们排序，即可以得到按照字典序排序的所有排列的有序集合。

如此，当我们知道当前的排列时，要获取下一个排列时，就可以范围有序集合中的下一个数（恰好比他大的）。比如，当前的排列时“123456879”，那么恰好比他大的下一个排列就是“123456897”。当当前的排列时最大的时候，说明所有的排列都找完了。

于是可以有下面计算下一个排列的算法：

设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>pj}（右边的数从右至左是递增的，因此k是所有大于pj的数字中序号最大者）　

3）对换pi，pk 　　

4）再将pj+1......pk-1pkpk+1......pn倒转得到排列p'=p1p2.....pj-1pjpn.....pk+1pkpk-1.....pj+1，这就是排列p的下一个排列。

上面解释的相当清楚，这里稍微提一些点

1、为什么要从右向左查找？因为这样能确保变化最小，即找到的数仅比现在的数大一丢丢。

2、为什么是找到第一个比右边小的数？因为这确保说明还有更大的数。

3、为什么要再从右向左找，找第一个比其大的数？因为从左到右是逐渐增加，第一个比起大，互换后，增加最少（一丢丢）

4、上面引用的第四步，为什么要倒转，互换？因为从左到右是逐渐增加，要只增加一丢丢。

上面在c++的stl库函数中，为next_permutation（按字典序，找排列组合的下一个元素）

如果觉得懂了，理解透了。可以尝试思考一下，prev_permutation（按字典序，找排列组合的上一个元素）

#include<iostream>
#include<algorithm> 
#include<string>
using namespace std;

int main()
{
	string s;
	getline(cin,s); 
	sort(s.begin(),s.end());
	do
	{
		cout<<s<<endl;
	}while(next_permutation(s.begin(),s.end()));
	return 0;
}

除了上面的排列方法，常见的排列算法有：递增进位制数法、递减进位制数法、邻位对换法

全排列算法

全排列算法

算法定义

相关阅读

栏目导航

推荐阅读

热门阅读