【转】全排列算法非递归实现和递归实现

                 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>
 8usingnamespace std;
 910 template<typename T>
11void permutation(T array[], int begin, int end)
12{
13int i;
1415if(begin == end){
16for(i = 0; i <= end; ++i){
17             cout<<array[i]<<"";
18        }
19         cout<<endl;
20return;
21     } else {
22//for循环遍历该排列中第一个位置的所有可能情况23for(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}
3031int main(int argc, char **argv)
32{
33int a[4] = {1, 2, 3, 4};
34     permutation(a, 0, sizeof(a) / sizeof(int) - 1);
3536return0;
37 }

                 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>
 9usingnamespace std;
1011//交换数组a中下标为i和j的两个元素的值12void swap(int *a,int i,int j)
13{
14     a[i]^=a[j];
15     a[j]^=a[i];
16     a[i]^=a[j];
17}
1819//将数组a中的下标i到下标j之间的所有元素逆序倒置20void reverse(int a[],int i,int j)
21{
22for(; i<j; ++i,--j) {
23        swap(a,i,j);
24    }
25}
2627void print(int a[],int length)
28{
29for(int i=0; i<length; ++i)
30         cout<<a[i]<<"";
31     cout<<endl;
32}
3334//求取全排列,打印结果35void combination(int a[],int length)
36{
37if(length<2) return;
3839bool end=false;
40while(true) {
41        print(a,length);
4243int i,j;
44//找到不符合趋势的元素的下标i45for(i=length-2; i>=0; --i) {
46if(a[i]<a[i+1]) break;
47elseif(i==0) return;
48        }
4950for(j=length-1; j>i; --j) {
51if(a[j]>a[i]) break;
52        }
5354        swap(a,i,j);
55         reverse(a,i+1,length-1);
56    }
57}
58int main(int argc, char **argv)
59{
60int a[4] = {1, 2, 3, 4};
61     combination(a, sizeof(a) / sizeof(int));
6263return0;
64 }

                 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>
 9usingnamespace std;
1011 template <typename BidirectionalIterator>
12void permutation(BidirectionalIterator array, int len)
13{
14     sort(array, array + len);
15do{
16for(int i = 0; i < len; ++i){
17             cout<<array[i]<<"";
18        }
19         cout<<endl;
20     }while(next_permutation(array, array + len));
21}
2223int main(int argc, char **argv)
24{
25int a[4] = {1, 2, 3, 4};
26     permutation(a, sizeof(a) / sizeof(int));
2728return0;
29 }

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