歡迎您光臨本站 註冊首頁

JAVA用遞歸實現全排列算法的示例代碼

←手機掃碼閱讀     niceskyabc @ 2020-07-06 , reply:0

求一個n階行列式,一個比較簡單的方法就是使用全排列的方法,那麼簡述以下全排列算法的遞歸實現。

首先舉一個簡單的例子說明算法的原理,既然是遞歸,首先說明一下出口條件。以[1, 2]為例

首先展示一下主要代碼(完整代碼在後面),然後簡述

  //對數組array從索引為start到最後的元素進行全排列  public void perm(int[]array,int start) {      if(start==array.length) { //出口條件        for(int i=0;i<array.length;i++) {  //        this.result[row][i] = array[i];          System.out.print(array[i]+" ");        }  //      System.out.print(++this.row+": ");  //      System.out.println("逆序數是:"+ this.against(array));        System.out.print(&#x27; &#x27;);      }      else {        for(int i=start;i<array.length;i++) {          swap(array,start,i); //交換數組array中索引為start與i的兩個元素          perm(array,start+1);           swap(array,start,i);        }      }    }

 

首先數組[1, 2]分析,在else的部分

調用了swap(array, 0,0)然後調用perm(array, 1)

  調用swap(array, 1, 1)然後調用perm(array, 2),然後在if裡面2 == 2成立,打印[1, 2]

  調用swap(array, 1,1)把之前交換的swap(array,1,1)復原,雖然看起來沒有變化

回到上一層

調用swap(array, 0, 1) 然後調用perm(array, 1)

  調用swap(array, 1, 1)然後調用perm(array, 2),然後在if裡面2 == 2成立,打印[2, 1]

  調用swap(array, 1,1)把之前交換的swap(array,1,1)復原,雖然看起來沒有變化

回到上一層

跳出循環,程序結束。

這就是對[1, 2]的全排列。

那麼放到一般情況,[1, 2, 3]呢?
 

調用了swap(array, 0,0)然後調用perm(array, 1)
 

  然後對[2, 3]進行全排列,其中輸出[1,2,3], [1, 3, 2]

再次調用swap(array,0,0)復原

調用了swap(array, 0,1)然後調用perm(array, 1)

  然後對[1,3]進行全排列,輸出[2,1,3], [2,3,1]

再次調用swap(array,0,1)復原

調用了swap(array, 0,2)然後調用perm(array, 1)

  然後對[2,1]進行全排列,輸出[3,2,1], [3,1,2]

再次調用swap(array,0,2)復原

更高階的就是同理了!

那麼我們的代碼如下:

  package matrix;    import java.util.Arrays;    public class Permutation {      /**     * author:ZhaoKe     * college: CUST     */    //當前打印的第幾個排列    private int row = 0;    //存儲排列的結果    private int[][] result;        public Permutation(int[] array) {      this.row = 0;      this.result = new int[this.factor(array.length)][array.length];    }        public int[][] getResult() {      return result;    }      //求數組a的逆序數    public int against(int a[]) {      int nn = 0;      for (int i = 0; i < a.length-1; i++) {        for (int j = i+1; j<a.length; j++) {          if (a[i] > a[j]) {            nn++;          }        }      }      return nn;    }      //排列數    public int factor(int a) {      int r = 1;      for (; a>=1; a--) {        r *= a;      }      return r;    }      public void perm(int[]array,int start) {      if(start==array.length) {        System.out.print((this.row+1)+": ");        for(int i=0;i<array.length;i++) {          this.result[row][i] = array[i];          System.out.print(array[i]+" ");        }        this.row++;        System.out.println("逆序數是:"+ this.against(array));        System.out.print(&#x27; &#x27;);      }      else {        for(int i=start;i<array.length;i++) {          swap(array,start,i);          perm(array,start+1);          swap(array,start,i);        }      }    }         public void swap(int[] array,int s,int i) {      int t=array[s];      array[s]=array[i];      array[i]=t;    }        public void printResult() {      for (int i = 0; i < result.length; i++) {          System.out.println(Arrays.toString(this.result[i]));      }    }        public static void main(String[] args) {      int[] a = {1, 2, 3};      Permutation p = new Permutation(a);      p.perm(a,0);      p.printResult();    }  }

 

運行該程序結果如下:

1: 1 2 3 逆序數是:0
  
 2: 1 3 2 逆序數是:1
  
 3: 2 1 3 逆序數是:1
  
 4: 2 3 1 逆序數是:2
  
 5: 3 2 1 逆序數是:3
  
 6: 3 1 2 逆序數是:2
  
 [1, 2, 3]
 [1, 3, 2]
 [2, 1, 3]
 [2, 3, 1]
 [3, 2, 1]
 [3, 1, 2]

 

                                                     

   


[niceskyabc ] JAVA用遞歸實現全排列算法的示例代碼已經有229次圍觀

http://coctec.com/docs/java/show-post-241464.html