全排列算法

谁借莪１个温暖的怀抱￠ 2022-05-14 07:41 190阅读 0赞

一、递归法

引用：[https://www.cnblogs.com/mengfanrong/p/3854044.html][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][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;
    }

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

[https_www.cnblogs.com_mengfanrong_p_3854044.html]: https://www.cnblogs.com/mengfanrong/p/3854044.html
[https_blog.csdn.net_cpfeed_article_details_7376132]: https://blog.csdn.net/cpfeed/article/details/7376132