image
【題目】設計一個遞歸算法生成n個元素{r1,r2,…,rn}的全排列置蜀。
【算法講解】：
設R={r1,r2,…,rn}是要進行排列的n個元素奈搜，Ri=R-{ri}。
集合X中元素的全排列記為perm(X)盯荤。
(ri)perm(X)表示在全排列perm(X)的每一個排列前加上前綴得到的排列媚污。
R的全排列可歸納定義如下：
當n=1時，perm(R)=(r)廷雅，其中r是集合R中唯一的元素耗美；
當n>1時，perm(R)由(r1)perm(R1)航缀，(r2)perm(R2)商架，…，(rn)perm(Rn)構(gòu)成芥玉。<font color="blue" face="方正宋黑簡體">實現(xiàn)思想：將整組數(shù)中的所有的數(shù)分別與第一個數(shù)交換蛇摸，這樣就總是在處理后n-1個數(shù)的全排列。</font>
【示例】
當n=3灿巧，并且E={a赶袄，b，c}抠藕，則：
perm(E)=a.perm({b,c}) + b.perm({a,c}) + c.perm({a,b})
perm({b,c})=b.perm(c) + c.perm(b)
a.perm({b,c})=a.b.perm(c) + a.c.perm(b)
? =a.b.c + a.c.b=(abc, acb)
我的代碼：
public class Main {
public static void main(String[] args){
char[] data="ABC".toCharArray();
f(data,0);
}
private static void f(char[] data,int k) {
if(k==data.length){//只剩下一個元素
for(int i=0;i<data.length;i++){
System.out.print(data[i]+" ");
}
System.out.println();
}
for(int i=k;i<data.length;i++){
{char c=data[k];data[k]=data[i];data[i]=c;}//試探
f(data,k+1);
{char c=data[k];data[k]=data[i];data[i]=c;}//回溯
}
}
}
關于回溯：
3個電燈串聯(lián)在一起饿肺，其中有個燈泡壞了，通過在燈泡正負極接上一根導線的方法來篩選出壞了的燈泡盾似，每次檢測下一燈泡時敬辣，必須先將連在上一燈泡的導線取下，保持在最初狀態(tài)零院，這就是回溯溉跃。
image
