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?
