2018-11-10-noj1324

noj-1324.png

这是开端。
然后产生了以下两个程序：

void perms1(int m)
{
    static int b[N]={0};
    static char use[N]={0};
    if(m >= n)
    {
        for(int i=0;i<n;i++)
            printf("%d ",b[i]);
        printf("\n");
        return ;
    }
    for(int i=0;i<n;i++)
    {
        if(use[i] == 0)
        {
            use[i] = 1;
            b[m] = a[i];
            dfs(m+1);
            use[i] = 0;
        }
    }
    return ;
}

void perms2(int m)
{
    if(m >= n)
    {
        for(int i=0;i<n;i++)
            printf("%d ",a[i]);
        printf("\n");
        return ;
    }
    for(int i=m,t=0;i<n;i++)
    {
        t = a[i]; a[i] = a[m]; a[m] = t;
        perms(m+1);
        t = a[i]; a[i] = a[m]; a[m] = t;
    }
    return ;
}

两个函数进行全排列后都可以按照字典序的顺序输出(不符合题意是因为后来历经多次修改，思想是相同的)。
比较 ：

空间：perms1为O(n),perms2为O(1)。
perms1使用了一倍的附加存储空间和相同数量的标记位。
perms2使用了一个变量用于交换。

时间：相同 。
递归层数相同。
函数内的循环次数不同，perms1更多的做了一些无用功。
由于交换，perms2在循环内的赋值操作比perms1多一倍。
实际测试中两个函数时间相差极小，大多数情况下perms2更快。
猜想：CPU的cache?