昨天在《算法競(jìng)賽入門經(jīng)典》中，挺劉汝佳介紹了C++的標(biāo)準(zhǔn)庫(kù)中有“求一個(gè)數(shù)字序列的下一個(gè)排列”的函數(shù)，然后自己思考了一下如何實(shí)現(xiàn)這個(gè)函數(shù)。
所謂下一個(gè)排列，比如對(duì)于序列1 2 3，它的下一個(gè)排列是1 3 2，再下一個(gè)是2 1 3……
首先想到的是通過一種規(guī)律性的總結(jié)，找到一種遞推或者其他方法，對(duì)原序列做相應(yīng)的變換，求得下一個(gè)排列。但是經(jīng)過大約十分鐘的思考之后，發(fā)現(xiàn)這種辦法似乎行不通。
后來仔細(xì)地回憶了求全排列的過程，有了這么一個(gè)思路：之所以不能夠直接求得下一個(gè)排列，就是因?yàn)椴恢来藭r(shí)dfs()運(yùn)行的情況，如果直接讓dfs()運(yùn)行到當(dāng)前的情況，問題迎刃而解。
于是便有了下面的代碼：
#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不重復(fù)數(shù)字的排列，如果數(shù)字同樣不重復(fù)，修改為任意一些數(shù)字的排列問題也是十分簡(jiǎn)單的。
posted on 2010-01-07 12:59
lee1r 閱讀(457)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
Programming Diary