Java 全排列——求n個不同元素的全排列

全排列問題

算法求解：

（圖檔來自網絡）

具體過程：

數列為{A，B，C}

1、第一個元素與第一個元素交換，即A與A交換，

（1）得到A {B，C}

（2）将{B，C}放在f()中遞歸，第一個元素與第一個元素交 換，即B與B交換，得到AB{C}

（3）将{C}放在f()中遞歸，C與C交換。因為k=data.length，是以輸出ABC

（4）結果輸出以後，進行回溯操作，從試探的結束回溯到開始的位置。從{C}開始。然後是{B，C}，第一個與第一個交換回來得到{B，C}，第一個和第二個交換（k與i++交換），得到{C，B}，第二個和第二個交換，結果不變，輸出ACB。

（5）{C，B}交換回來，序列恢複為原來的ABC。

2、第一個元素和第二個元素交換，即A與B交換，

（1）得到B{A，C}

（2）将{A，C}放在f()中遞歸，第一個元素與第一個元素交換，即A與A交換，得到BA{C}

（3）将{C}放在f()中遞歸，C與C交換。因為k=data.length，是以輸出BAC

（4）結果輸出以後，進行回溯操作，從試探的結束回溯到開始的位置。從{C}開始。然後是{A，C}，第一個與第一個交換回來得到{A，C}，第一個與第二個交換，得到{C，A}，第二個與第二個交換，結果不變，輸出BCA。

（5）{C，A}交換回來為{A，C}，B{A，C}交換回來為ABC。

3、第一個元素和第三個元素交，

（1）得到C{B，A}

（2）将{B，A}放在f()中遞歸，第一個元素與第一個元素交換，得到CB{A}

（3）将{A}放在f()中遞歸。因為k=data.length，是以輸出CBA。

（4）結果輸出後，進行回溯操作，從試探的結束回溯到開始位置。從{A}開始。然後是{B，A}，第一個與第一個交換回來得到{B，A}，第一個和第二個交換，得到{A，B}，第二個與第二個交換，結果不變，最後輸出CAB。

（5）{A，B}交換回來為{B，A}，C{B，A}交換回來為ABC。

基本思路：

先進行試探，然後遞歸，等到k=data.length後，輸出結果，再進行回溯，回溯過程中的子集再進行試探、遞歸操作，輸出後不要忘記回溯操作。

//求n個元素的全排列
public class C {
	public static void f(char[] data,int k) {
		if(k==data.length) {
			for(int j=0;j<data.length;j++)
				System.out.print(data[j]+" ");
			System.out.println();
		}
		for(int i=k;i<data.length;i++) {
			//試探
			char t=data[k];
			data[k]=data[i];
			data[i]=t;
			//遞歸
			f(data, k+1);
			//回溯
			char m=data[k];
			data[k]=data[i];
			data[i]=m;
		}
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		char[] data="ABC".toCharArray();
		f(data,0);
	}
}