[算法]全排列算法C++递归实现

soloforce

当做练习C++的小玩艺，高手们就不必浪费时间了：）
----------------------------------------------------------------
思路：把各个元素逐个插入到已有排列中所有可能的位置，当得到的目标排列长度等于题给要求排列长度时，把该排列保存起来，即为一个成功的排列。

实现：C++， vector， 递归

效率：设每插入一次为一个基本运算，则时间复杂度为 O(n!) ;  加上vector在插入时又有开销，时间效率不高。 若不把结果输出到屏幕，则AMD XP 1600+ / 1G mem 的运行时间如下：

8个元素的全排列：
~/coding/cpp $ time ./a.out
real        0m0.154s
user        0m0.134s
sys        0m0.005s

------------------------
9个元素的全排列：
~/coding/cpp $ time ./a.out

real        0m1.409s
user        0m1.208s
sys        0m0.060s

------------------------
10个元素的全排列：
~/coding/cpp $ time ./a.out

real        0m13.858s
user        0m11.227s
sys        0m0.669s

[php]
#include <iostream>
#include <vector>
#define arr_size(A) (sizeof(A)/sizeof(A[0]))
using namespace std;

template<typename Type>
vector<Type>& permutation(vector<Type> des, vector<Type> src)
{
    static vector<Type> result;
    if( src.empty() ){
        //append a permutation to result-vector
        result.insert(result.end(), des.begin(), des.end());
        return result;
    }
    Type curr=src.back();
    src.pop_back();
    for(typename vector<Type>::iterator it=des.begin();it<des.end()+1; it++){
        //try to insert an item to any possible position
        it=des.insert(it,curr);
        permutation(des,src);
        //remove it for next insertion
        des.erase(it);
    }
    return result;
}

int main()
{
    int arr[]={1,2,3,4,5,6,7,8,9,10};
    vector<int>vi(arr,arr+arr_size(arr));
    vector<int>result=permutation(vector<int>(),vi);

    // print results to stdout
    for(vector<int>::iterator it=result.begin(); it<result.end();){
        for(int i=0; i<arr_size(arr); i++){
            cout<<*it<<" ";
            it++;
        }
        cout<<endl;
    }
    cout<<"permutations count: "<<result.size()/arr_size(arr)<<endl;
}
[/php]

yuhch123

iostream不是一般的慢，改成stdio.h，用scanf和printf会快很多吧

Iambitious

1.         public boolean nextPermutation(int[] a) {
2.                 int i, j;
3.                 for (i = a.length - 1; i > 0; i--) {
4.                         if (a[i] > a[i - 1]) {
5.                                 break;
6.                         }
7.                 }
8.                 i--;
9.                 if (i == -1)
10.                         return false;
11.                 for (j = a.length - 1; j >= 0; j--) {
12.                         if (a[j] > a[i])
13.                                 break;
14.                 }
15.                 int t = a[j];
16.                 a[j] = a[i];
17.                 a[i] = t;
18.                 for (i = i + 1, j = a.length - 1; i < j; i++, j--) {
19.                         t = a[i];
20.                         a[i] = a[j];
21.                         a[j] = t;
22.                 }
23.                 return true;
24.         }

复制代码

字典序数法：c++ stl中的next_permutation的实现方法，应该是综合情况下最快的产生全排列的算法(尤其在有重复数据的情况下)。

Iambitious

字典序数法是按照“字典”顺序给出的全排列，有一个排列p1,p2,...pn生成下一个排列的算法如下：
1。求满足关系式p(j-1) < p(j)的j的最大值，设为i
2。求满足关系式p(i-1) < p(k)的k的最大值，设为j
3。p(i-1)与p(j)互相交换，得到新的数列
4。在把新得到的数列从第i个位置到最后一个位置，全部逆转，所得到的数列就是下一个字典序数的排列。
初始状态为p1<=p2<=p3<=...pn
终止状态为pn>=p(n-1)>=...>=p2>=p1

soloforce

又掌握了一种方法，谢谢Iambitious了。
不过我看字典法每求一个排列要比较、交换的次数好像很多，对于无重复数据的排列应该也不是效率最高的算法吧; 如果重复数据比较多，那的确很快，而且不会产生重复输出。

Iambitious

在非插入全排列算法里面应该是最快的，其他的方法需要比较的次数更多，插入全排列的生成算法，如果用链表来实现的话，应该是最快的。

demonarea

以前写过一个非递归的，拿出来献丑一下，因为本人是英语专业，写的不好大家多包涵，主要思想还是和lz一样的，只是把递归改成非递归而已，从算法思想上来讲自然是Iambitious的好。

2. #include<stdio.h>
3. #include<string.h>
4. #define N 12
5. #define pop(str) strcpy(str, stack[--top])
6. #define push(str) strcpy(stack[top++], str)
7. #define permute(str, i)                                               \
8.         ({int t; t = str[i]; str[i] = str[i-1]; str[i-1] = t; str;})
9. static char str[N+1], stack[N*(N-1)/2+1][N+1];
10. static int len, top;
12. int main ()
13. {
14.         push("1");            /* push the root */
15.         while( top > 0 ) {    /* exit when all leaves visited */
16.                 pop(str);
17.                 if( (len = strlen(str)) >= N-1 )
18.                         printf( "%s\n", str ); /* reach the leaf */
19.                 else {
20.                         for( int i = len+1; i >= 1; i-- )
21.                                 str[i] = str[i-1];
22.                         str[0] = len + '1';
23.                         push(str);
24.                         for( int i = 1; i <= len; i++ ) /* push brothers */
25.                                 push( permute( str, i ) );
26.                 }
27.         }
28.         return 0;
29. }

复制代码