[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;
} 


[yuhch123]

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

[Iambitious]

	public boolean nextPermutation(int[] a) {
		int i, j;
		for (i = a.length - 1; i > 0; i--) {
			if (a[i] > a[i - 1]) {
				break;
			}
		}
		i--;
		if (i == -1)
			return false;
		for (j = a.length - 1; j >= 0; j--) {
			if (a[j] > a[i])
				break;
		}
		int t = a[j];
		a[j] = a[i];
		a[i] = t;
		for (i = i + 1, j = a.length - 1; i < j; i++, j--) {
			t = a[i];
			a[i] = a[j];
			a[j] = t;
		}
		return true;
	}

字典序数法：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的好。

#include<stdio.h>
#include<string.h>
#define N 12
#define pop(str) strcpy(str, stack[--top])
#define push(str) strcpy(stack[top++], str)
#define permute(str, i)                                               \
        ({int t; t = str[i]; str[i] = str[i-1]; str[i-1] = t; str;})
static char str[N+1], stack[N*(N-1)/2+1][N+1];
static int len, top;

int main ()
{
        push("1");            /* push the root */
        while( top > 0 ) {    /* exit when all leaves visited */
                pop(str);
                if( (len = strlen(str)) >= N-1 ) 
                        printf( "%s\n", str ); /* reach the leaf */
                else {
                        for( int i = len+1; i >= 1; i-- )
                                str[i] = str[i-1];
                        str[0] = len + '1';
                        push(str);
                        for( int i = 1; i <= len; i++ ) /* push brothers */
                                push( permute( str, i ) );
                }
        }
        return 0;
}