全排列算法及其证明

时间：2010-07-23 来源：Z_Q_2010

可以套用全排列的方法来枚举一个问题的所有情况，然后筛选出满足要求的一组数据

#include<stdio.h>
#include<algorithm>
using std::swap;

const int N=3;
int s[N];

void dfs(int depth)
{
    if(depth==N)
    {
        for(int i=0;i<N;i++)
        {
            printf("%4d",s[i]);
        }
        printf("\n");
        return ;
    }

    for(int i=depth;i<N;i++)
    {
        swap(s[depth],s[i]);
        dfs(depth+1);
        swap(s[depth],s[i]);
    }
}

int main()
{
    for(int i=0;i<N;i++)
        s[i]=i;

    dfs(0);

    return 0;
}

全排列的数学证明：

令E={e1,e2,e3……en}表示n个元素的集合,Ei表示E中除去元素i后的集合,prem(X)表示集合X中所有元素的所有全排列方式

例如:n=3,E={a,b,c}

prem(E)=a*prem({b,c})+b*prem({a,c})+c*prem({a,b})=a*(b*prem({c})+c*prem({b}))+b*(a*prem({c})+c*prem({a}))+c*(a*prem({b})+b*prem({a}))=a*(bc,cb)+b*(ac,ca)+c*(ab,ba)=(abc,acb,bac,bca,cab,cba)

由于计算机内存是线性的，所以在编程处理E集合的元素序列中通过交换在序列中的第depth位置的元素来实现全排列，这也可以看成是一个深度优先搜索，在一个序列上从前往后依次搜索满足要求的元素

相关阅读更多 +