昨天在《算法競賽入門經典》中，挺劉汝佳介紹了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 閱讀(453)
評論(0) 編輯 收藏 引用 所屬分類:
Programming Diary