某一次面試時的上機題,準備較充分的情況下完成的代碼。很久沒寫算法類的代碼了,放上來僅做保留友善檢視。
package permutation;
import java.util.Iterator;
import java.util.TreeSet;
/**
* Permutation.class
* @author vincent
* 2007-07-28
*/
public class Permutation {
private static int count = 0; //計數器
private static TreeSet<String> set = new TreeSet<String>(); //儲存符合要求的序列且不含重複元素
/**
* 将arr字元數組src和dest位置的字元進行交換
* @param arr
* @param src
* @param dest
*/
public static void swap(char[] arr , int src , int dest){
char temp = arr[src];
arr[src] = arr[dest];
arr[dest] = temp;
}
/**
* 判斷arr序列是否符合要求
* 條件1:4不能在第三位
* 條件2:3與5不能相連
* @param arr
* @return
*/
public static boolean validate(char[] arr){
String temp = String.valueOf(arr);
return temp.charAt(2)!='4' && temp.indexOf("35")==-1 && temp.indexOf("53")==-1;
}
/**
* 對字元進行全排列(遞增)
* 實作思路:345 -> 354 -> 435 -> 453 -> 534 - > 543
* 可以看出先将後面的45排列好後有2種:45和54,
* 把3加進來進行排列其實就是在這兩種組合中循環的交換便能實作遞增的全排列
* @param arr
* @param begin
* @param end
*/
public static void perm(char[] arr , int begin , int end){
if(begin == end){
if(validate(arr)){
set.add(String.valueOf(arr));
}
return ;
}
for (int i = begin; i <= end; i++) {
swap(arr , begin , i);
perm(arr , begin+1 , end);
swap(arr , begin , i);
}
}
/**
* 列印所有排列
* 每行10個
*/
public static void showAllPermutation(){
Iterator<String> it = set.iterator();
while(it.hasNext()){
count ++;
System.out.print(it.next()+" ");
if(count % 10 == 0){
System.out.println();
}
}
System.out.println("\n總共有 "+count+" 種");
}
/**
* 主函數
*/
public static void main(String[] args) {
char[] arr = {'1','2','2','3','4','5'};
// char[] arr = {'1','2','3'};
Permutation.perm(arr, 0, arr.length-1);
Permutation.showAllPermutation();
}
}