JAVA用递归实现全排列算法的示例代码

求一个n阶行列式，一个比较简单的方法就是使用全排列的方法，那么简述以下全排列算法的递归实现。

首先举一个简单的例子说明算法的原理，既然是递归，首先说明一下出口条件。以[1, 2]为例

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

//对数组array从索引为start到最后的元素进行全排列  public void perm(int[]array,int start) {
    if(start==array.length) { //出口条件
      for(int i=0;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 {

  
  //当前打印的第几个排列
  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[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

运行该程序结果如下：

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]

以上就是JAVA用递归实现全排列算法的示例代码的详细内容，更多关于JAVA递归实现全排列的资料请关注考高分网其它相关文章！