快捷導(dǎo)航

JAVA用遞歸實現(xiàn)全排列算法的示例代碼

更新時間：2020年07月03日 14:17:57 作者：心拍數(shù)#0822

這篇文章主要介紹了JAVA用遞歸實現(xiàn)全排列算法的相關(guān)資料，文中示例代碼非常詳細(xì)，幫助大家更好的理解和學(xué)習(xí)，感興趣的朋友可以了解下

求一個n階行列式，一個比較簡單的方法就是使用全排列的方法，那么簡述以下全排列算法的遞歸實現(xiàn)。

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

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

//對數(shù)組array從索引為start到最后的元素進(jìn)行全排列  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("逆序數(shù)是："+ this.against(array));
      System.out.print('\n');
    }
    else {
      for(int i=start;i<array.length;i++) {
        swap(array,start,i); //交換數(shù)組array中索引為start與i的兩個元素
        perm(array,start+1); 
        swap(array,start,i);
      }
    }
  }

首先數(shù)組[1, 2]分析，在else的部分

調(diào)用了swap(array, 0,0)然后調(diào)用perm(array, 1)

　　調(diào)用swap(array, 1, 1)然后調(diào)用perm(array, 2)，然后在if里面2 == 2成立，打印[1, 2]

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

回到上一層

調(diào)用swap(array, 0, 1) 然后調(diào)用perm(array, 1)

　　調(diào)用swap(array, 1, 1)然后調(diào)用perm(array, 2)，然后在if里面2 == 2成立，打印[2, 1]

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

回到上一層

跳出循環(huán)，程序結(jié)束。

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

那么放到一般情況，[1, 2, 3]呢？

調(diào)用了swap(array, 0,0)然后調(diào)用perm(array, 1)

　　然后對[2, 3]進(jìn)行全排列，其中輸出[1,2,3]， [1, 3, 2]

再次調(diào)用swap(array,0,0)復(fù)原

調(diào)用了swap(array, 0,1)然后調(diào)用perm(array, 1)

　　然后對[1,3]進(jìn)行全排列，輸出[2,1,3], [2,3,1]

再次調(diào)用swap(array,0,1)復(fù)原

調(diào)用了swap(array, 0,2)然后調(diào)用perm(array, 1)

　　然后對[2,1]進(jìn)行全排列，輸出[3,2,1], [3,1,2]

再次調(diào)用swap(array,0,2)復(fù)原

更高階的就是同理了！

那么我們的代碼如下：

package matrix;

import java.util.Arrays;

public class Permutation {

  /**
   * author:ZhaoKe
   * college: CUST
   */
  //當(dāng)前打印的第幾個排列
  private int row = 0;
  //存儲排列的結(jié)果
  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;
  }

  //求數(shù)組a的逆序數(shù)
  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;
  }

  //排列數(shù)
  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("逆序數(shù)是："+ this.against(array));
      System.out.print('\n');
    }
    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();
  }
}

運行該程序結(jié)果如下：

1: 1 2 3 逆序數(shù)是：0

2: 1 3 2 逆序數(shù)是：1

3: 2 1 3 逆序數(shù)是：1

4: 2 3 1 逆序數(shù)是：2

5: 3 2 1 逆序數(shù)是：3

6: 3 1 2 逆序數(shù)是：2

[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 2, 1]
[3, 1, 2]