网页爱好者

有时我们需要枚举一组对象的全排列。例如，给你一个字符集合{'a', 'd', 'e'}，列出他所有的可能排列情况则应该是：

ade
aed
dae
dea
eda
ead

解决排列问题的最直观的方法还是乘法原理中列出的办法。对于一个集合，我们可以按照下列方法找到一个排列：

• 从N个元素中选取第一个元素
• 从剩下的N-1个元素中选取第二个元素
• ......
• 从剩下的2个元素中选取一个元素
• 选取最后一个元素

 问题是，上面的算法看起来更象一个递归算法，而这样的递归算法在元素个数比较多时，很容易造成堆栈溢出。因此需要找到一种非递归的算法。

分析

根据排列组合的知识，我们知道一个包含N个元素的集合，其全排列有N!种情况，能不能找到一种算法，让我们可以找到一个从0到N!-1之间取值的“下标”，每个下标可以直接得到一个排列情况？这样，我们就可以用一个简单的for循环，打印出所有的排列情况。

答案是肯定的，通过简单的分析，我们就可以建立一个从一个整数到一种排列的一一对应关系。

让我们回忆一下10进制数的知识，对于一个N位的10进制数，每个位上的数都可以在0,...,9之间的一个数字中选取，第n位的数的基数为10^n-1。我们通过变化每位上的数字，就可以遍历0到10^N-1之间的每个数。更特别的是，一个N位的10进制数X，其第n位上的数字X_n可以通过下面的式子得到:

X_n=(X/10^n-1)%10

比较一下这个10进制数和前面的全排列，我们发现他们所不同的是10进制数每位的可选数字的个数是固定的，而我们的全排列问题则可选元素个数越来越小。

与10进制数相类似，我们把前面步骤中的每个选择的下标放到一起，构成一个N位数。如果第n次我们选择了N-n个元素中的第k个，则我们把这个N位数的N-n位设置为k。但是，由于可选元素个数越来越少，我们的这个N位数不能象10进制数那样使用一个常数的n-1次方来做基，由于可选元素的个数每次减少1，很容易我们可以想到，如果我们定义第n位的基为(n-1)!，和10进制数将是类似的。

我们记这个N位数的第k位为n_k则我们知道这个N位数的值为：

(N)₁₀=∑n_k*(k-1)!

根据这个式子，我们知道根据N的值，得到每位上的下标为

n_k=(N/(k-1)!)%k

我们可以根据这个策略得到每次选择的下标。

实现

下面例子演示了打印几个字符全排列的算法：

#include <iostream>
using namespace std;

//计算n的阶乘
int factor(int n)
...{
    int result=1;
    for(;n>0;n--)
    ...{
        result *=n;
    }
    return result;
}

//把数组pT中的元素从start到last前移一个位置
template<typename T>
void copy(T* pT, int start, int last)
...{
    int pos;
    for(pos=start; pos <=last; pos++)
    ...{
        pT[pos-1]=pT[pos];
    }
}
/**//*
 * 获得一个排列，元素数组放在in中，结果在out中，count是in中元素的个数, index是下标
 */
template<typename T>
int GetPermutation(const T * in, T* out, int count, int index)
...{
    int pos;
    int m;
    typedef const T* CPT;
    //°ÑÔªËصÄÖ¸Õë·Åµ½Êý×éÖÐÒÔ±¸Ñ¡Ôñ
    CPT* pcopy = new CPT[count];
    for(pos=0; pos < count; pos++)
    ...{
        pcopy[pos] = in+pos;
    }

    int base=factor(count-1);
    for(m=count-1; m>0; m--)
    ...{
        out[m]= *pcopy[index/base];
        copy(pcopy, 1+index/base,m);
        index = index %base;
        base = base/m;
    }
    out[0]=*pcopy[0];
    delete []pcopy;
    return 0;
}

int main(int, char*[])
...{
    char arr[]=...{'a','b','c','d','e'};
    char arr1[6];
    arr1[5] =0;
    int i;
    for(i=0; i < 120; i ++)
    ...{
        GetPermutation(arr, arr1,5,i);
        cout << arr1 << endl;
    }
    cin>>arr[0];
    return 0;
};

诸如八皇后问题等常见问题都可以用这个方法解决