如何用JAVA递归编写全排列算法示例代码？

本文共计1373个文字，预计阅读时间需要6分钟。

求一个N阶行列式的简单方法就是使用全排列的公式，以下简要概述全排列算法的递归实现。

首先，举一个简单的例子说明算法的原理。假设我们要计算一个3阶行列式：

\[ \begin{vmatrix} a & b & c \\ d & e & f \\ g & h & i \end{vmatrix} \]

我们可以按照以下步骤计算：

1. 以a为对角线元素，将剩下的行列式分为两部分，一部分是a所在行去掉第一列，另一部分是去掉a所在列的剩余行列式。

2.计算去掉a所在行和列后的行列式，即：

\[ \begin{vmatrix} b & c \\ h & i \end{vmatrix} \]

3. 递归计算这个2阶行列式。

递归实现步骤如下：

1. 如果行列式是1阶的，直接返回该元素的值。

2.否则，选择一个元素（例如a），计算其余元素的行列式（递归调用）。

3.将所有元素按照全排列进行排列，并计算每种排列对应的行列式的乘积。

4.将所有乘积相加得到最终结果。

下面是一个简单的递归函数实现：

python

def determinant(matrix): # 基本情况：1阶行列式 if len(matrix)==1: return matrix[0][0]

# 基本情况：2阶行列式 if len(matrix)==2: return matrix[0][0]*matrix[1][1] - matrix[0][1]*matrix[1][0]

# 递归计算 result=0 for c in range(len(matrix)): sub_matrix=[row[:c] + row[c+1:] for row in matrix[1:]] sign=(-1)**c result +=sign * matrix[0][c] * determinant(sub_matrix)

return result

使用这个函数，可以计算任意N阶行列式的值。

求一个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('\n'); } 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('\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(); } }

运行该程序结果如下：

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递归实现全排列的资料请关注易盾网络其它相关文章！