昨天在《算法竞赛入门经典》中，挺刘汝佳介绍了C++的标准库中有“求一个数字序列的下一个排列”的函数，然后自己思考了一下如何实现这个函数。
所谓下一个排列，比如对于序列1 2 3，它的下一个排列是1 3 2，再下一个是2 1 3……
首先想到的是通过一种规律性的总结，找到一种递推或者其他方法，对原序列做相应的变换，求得下一个排列。但是经过大约十分钟的思考之后，发现这种办法似乎行不通。
后来仔细地回忆了求全排列的过程，有了这么一个思路：之所以不能够直接求得下一个排列，就是因为不知道此时dfs()运行的情况，如果直接让dfs()运行到当前的情况，问题迎刃而解。
于是便有了下面的代码：
#include<stdio.h>
const long maxn=108;
long n,a[maxn];
bool used[maxn],first,ans;
void dfs(long dep)
{
if(dep>n)
{
if(first) first=false;
else
{
bool f=true;
for(long i=1;i<=n;i++)
{
if(f) f=false;
else putchar(' ');
printf("%ld",a[i]);
}
putchar('\n');
ans=true;
}
return;
}
for(long i=1;i<=n&&!ans;i++)
if(first)
{
i=a[dep];
dfs(dep+1);
used[i]=false;
}
else if(!used[i])
{
used[i]=true;
a[dep]=i;
dfs(dep+1);
used[i]=false;
}
}
int main()
{
//*
freopen("program.in","r",stdin);
freopen("program.out","w",stdout);
//*/
n=0;
while(scanf("%ld",&a[n+1])==1) n++;
// Read In
ans=false;
first=true;
for(long i=1;i<=n;i++) used[i]=true;
dfs(1);
if(!ans) printf("No answer\n");
return 0;
}
这段代码只适用于1-n不重复数字的排列，如果数字同样不重复，修改为任意一些数字的排列问题也是十分简单的。
posted on 2010-01-07 12:59
lee1r 阅读(417)
评论(0) 编辑 收藏 引用 所属分类:
Programming Diary