生成全排列的两种方式

生成全排列的两种方式

本篇随笔简单介绍一下生成全排列问题的两种方式。

---

第一种：手写深搜函数

（详见蒟蒻博客：全排列问题）

代码如下：

void dfs(int x)
{
    if(x==n+1)
    {
        for(int i=1;i<=n;i++)
            printf("%d ",a[i]);
        puts("");
        return;
    }
    for(int i=1;i<=n;i++)
    {
        if(!v[i])
        {
            a[x]=i;
            v[i]=1;
            dfs(x+1);
            v[i]=0;
        }
    }
}

---

第二种：C++ STL

使用函数：next_permutation();

(permutation就是英文中：排列、排列方式的意思。这样理解译文之后就会比较好记)

上传参数是首尾指针。

代码：

void fun(int n)
{
    for(int i=1;i<=n;i++)
        a[i]=i;
    do
    {
        for(int i=1;i<=n;i++)
            printf("%d ",a[i]);
        puts("");
    }while(next_permutation(a+1,a+n+1));
}