搜尋此網誌

2015年2月12日 星期四

回朔法(Backtracking)求所有數字的排列


public class NumberPermutation {

    public static void main(String[] args){
      /*
      * 123,132,213,231,312,321
      */
     int[] numbers = new int[] {1,2,3};
     backTrackPermutation(numbers ,0 ,2);
    }
    
    private static void backTrackPermutation(int[] numbers,int startIdx , int endIdx){
 
 if(startIdx == endIdx){
     printArray(numbers);
 }else{
     for(int j = startIdx; j <= endIdx ; j++){
  swap(numbers, startIdx , j);
  backTrackPermutation(numbers ,startIdx+1, endIdx);
  swap(numbers, startIdx , j);
     }
     
 }
 
    }
    
    private static void swap(int[] numbers,int idx1 , int idx2){
 int temp = numbers[idx1];
 numbers[idx1] = numbers[idx2];
 numbers[idx2] = temp;
    }
    
    private static void printArray(int[] numbers){
 for(int i = 0 ; i < numbers.length ; i++){
     System.out.print(numbers[i]);
 }
 System.out.println();
    }
    
}