【转】全排列算法非递归实现和递归实现-阿里云开发者社区

来源：http://blog.csdn.net/e3399/article/details/7543861

（一）递归的全排列算法

（A、B、C、D）的全排列为

1、A后面跟（B、C、D）的全排列

2、B后面跟（A、C、D）的全排列

3、C后面跟（A、B、D）的全排列

4、D后面跟（A、B、C）的全排列

而对1中的（B、C、D）照样可以按照上面的形式进行分解。

 1 /**********************************************************************
 2  * Compiler: GCC
 3  * Last Update: Mon 07 May 2012 07:08:58 PM CST
 4  * File Name: 1.cpp
 5  * Description: 利用stl中的next_permutation进行全排列
 6  ************************************************************************/
 7 #include <iostream>
 8 using namespace std;
 9 
10 template<typename T>
11 void permutation(T array[], int begin, int end)
12 {
13     int i;
14 
15     if(begin == end){
16         for(i = 0; i <= end; ++i){
17             cout<<array[i]<<" ";
18         }
19         cout<<endl;
20         return;
21     } else {
22         //for循环遍历该排列中第一个位置的所有可能情况
23         for(i = begin; i <= end; ++i) {
24             swap(array[i], array[begin]);
25             permutation(array, begin + 1, end);
26             swap(array[i], array[begin]);
27         }
28     }
29 }
30 
31 int main(int argc, char **argv)
32 {
33     int a[4] = {1, 2, 3, 4};
34     permutation(a, 0, sizeof(a) / sizeof(int) - 1);
35 
36     return 0;
37 }

View Code

（二）非递归全排列算法,即按字典序排列算法。

基本思想是:
    1.对初始队列进行排序，找到所有排列中最小的一个排列Pmin。
    2.找到刚刚好比Pmin大比其它都小的排列P(min+1)。
    3.循环执行第二步,直到找到一个最大的排列,算法结束。
如排列ABCDE，这是所有排列中最小的一个排列，刚好比ABCDE大的排列是：ABCED。
算法如下：
给定已知序列P = A1A2A3.....An
对P按字典排序，得到P的一个最小排列Pmin = A1A2A3....An ，满足Ai > A(i-1) (1 < i <= n)
从Pmin开始,找到刚好比Pmin大的一个排列P(min+1)，再找到刚好比P(min+1)大的一个排列，如此重复。
1.从后向前（即从An->A1）,找到第一对为升序的相邻元素，即Ai < A(i+1)。
若找不到这样的Ai，说明已经找到最后一个全排列，可以返回了。
2.从后向前,找到第一个比Ai大的数Aj，交换Ai和Aj。
3.将排列中A(i+1)A(i+2)....An这个序列的数逆序倒置，即An.....A(i+2)A(i+1)。因为由前面第1、2可以得知，A(i+1)>=A(i+2)>=.....>=An,这为一个升序序列，应将该序列逆序倒置，所得到的新排列才刚刚好比上个排列大。
4.重复步骤1-3,直到返回。

这个算法是C++ STL算法next_permutation的思想。

 1 /**********************************************************************
 2  * Compiler: GCC
 3  * Last Update: Mon 07 May 2012 07:08:58 PM CST
 4  * File Name: 1.cpp
 5  * Description:
 6  ************************************************************************/
 7 #include <iostream>
 8 #include <cstring>
 9 using namespace std;
10 
11 //交换数组a中下标为i和j的两个元素的值
12 void swap(int *a,int i,int j)
13 {
14     a[i]^=a[j];
15     a[j]^=a[i];
16     a[i]^=a[j];
17 }
18 
19 //将数组a中的下标i到下标j之间的所有元素逆序倒置
20 void reverse(int a[],int i,int j)
21 {
22     for(; i<j; ++i,--j) {
23         swap(a,i,j);
24     }
25 }
26 
27 void print(int a[],int length)
28 {
29     for(int i=0; i<length; ++i)
30         cout<<a[i]<<" ";
31     cout<<endl;
32 }
33 
34 //求取全排列,打印结果
35 void combination(int a[],int length)
36 {
37     if(length<2) return;
38 
39     bool end=false;
40     while(true) {
41         print(a,length);
42 
43         int i,j;
44         //找到不符合趋势的元素的下标i
45         for(i=length-2; i>=0; --i) {
46             if(a[i]<a[i+1]) break;
47             else if(i==0) return;
48         }
49 
50         for(j=length-1; j>i; --j) {
51             if(a[j]>a[i]) break;
52         }
53 
54         swap(a,i,j);
55         reverse(a,i+1,length-1);
56     }
57 }
58 int main(int argc, char **argv)
59 {
60     int a[4] = {1, 2, 3, 4};
61     combination(a, sizeof(a) / sizeof(int));
62 
63     return 0;
64 }

View Code

用STL实现：

STL有一个函数next_permutation()，它的作用是如果对于一个序列，存在按照字典排序后这个排列的下一个排列，那么就返回true且产生这个排列，否则返回false。

 1 /**********************************************************************
 2  * Compiler: GCC
 3  * Last Update: Mon 07 May 2012 07:08:58 PM CST
 4  * File Name: 1.cpp
 5  * Description: 利用stl中的next_permutation进行全排列
 6  ************************************************************************/
 7 #include <iostream>
 8 #include <algorithm>
 9 using namespace std;
10 
11 template <typename BidirectionalIterator>
12 void permutation(BidirectionalIterator array, int len)
13 {
14     sort(array, array + len);
15     do{
16         for(int i = 0; i < len; ++i){
17             cout<<array[i]<<" ";
18         }
19         cout<<endl;
20     }while(next_permutation(array, array + len));
21 }
22 
23 int main(int argc, char **argv)
24 {
25     int a[4] = {1, 2, 3, 4};
26     permutation(a, sizeof(a) / sizeof(int));
27 
28     return 0;
29 }

View Code

文章参考来源：http://blog.csdn.net/hackbuteer1/article/details/6657435

http://plutoblog.iteye.com/blog/976216

http://blog.csdn.net/aipb2008/article/details/2227490

有一定约束条件的全排列

http://blog.csdn.net/hackbuteer1/article/details/6657435

对数1，2，3，4，5要实现全排序。要求4必须在3的左边，其它的数位置随意。

思路：首先使用上面的2种方法之一实现全排列，然后对全排列进行筛选，筛选出4在3左边的排列。

 1 #include "iostream"
 2 #include "algorithm"
 3 using namespace std;
 4 
 5 void permutation(int* a,int length)
 6 {
 7     int i,flag;
 8     sort(a,a+length);
 9     do
10     {
11         for(i=0;i<length;i++)
12         {
13             if(a[i]==3)
14                 flag=1;
15             else if(a[i]==4)             //如果3在4的左边，执行完代码，flag就是2
16                 flag=2;
17         }
18         if(flag==1)          //如果4在3的左边，执行完代码，flag就是1
19         {
20             for(i=0;i<length;i++)
21                 cout<<a[i];
22             cout<<endl;
23         }
24     }while(next_permutation(a,a+length));
25 
26 }
27 int main(void)
28 {
29     int i,a[5];
30     for(i=0;i<5;i++)
31         a[i]=i+1;
32     printf("%d以内所有4在3左边的全排列结果为：\n",i);
33     permutation(a,5);
34     system("pause");
35     return 0;
36 }

View Code

下面的分析来自C语言程序设计-顾志华：（page251）

对一组数穷尽所有排列，还有更好的方法。将一个排列看成一个长整数，则每个排列对应一个不同的长整数，所有可能的排列对应着一组有限的整数。将这组整数按从小到大的顺序排成一个数列，从对应最小的整数开始，按数列的递增顺序顺序逐一列举每个排列对应的每一个整数，这能更有效地完成排列的穷举。从一个排列找出对应数列的下一个排列可在当前排列的基础上作部分调整来实现。倘若当前排列为1、2、4、8、7、6、5、3，并令其对应的长整数为12487653。要寻找比长整数12487653更大的排列，可从该排列的最后一个数字顺序向前逐位考察，当发现排列中的某个数字比前一个数字大时，如本例中的8比它的前一个数字4大，这说明还有对应更大整数的排列。但为了顺序从小到大列举出所有的排列，不能立即调整的太大，如本例中将数字8与4交换得到的序列12847653就不是排列12487653的下一个序列。为得到排列12487653的下一个排列，应从已考察过的那部分数字中选出比数字4大，但又是它们中最小的那一个数字，比如数字5，该数字也是从后向前考察过程中第一个比4大的数字。5与4交换后，得到排列12587643，在前面数字1、2、5固定的情况下，还应选择对应最小整数的那个序列。为此还需将后面那部分数字的排列顺序颠倒，如将数字8、7、6、4、3的顺序颠倒，得到排列1、2、5、3、4、6、7、8，这才是排列1、2、4、8、7、6、5、3的下一个排列。