最新下载
热门教程
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
JAVA用递归如何实现全排列算法 JAVA用递归实现全排列算法代码示例
时间:2020-07-03 编辑:袖梨 来源:一聚教程网
JAVA用递归如何实现全排列算法?本篇文章小编给大家分享一下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 { /** * 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; ja[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]
相关文章
- SpringBoot自定义bean绑定解析 10-24
- Javaweb工程运行报错HTTP Status 404解决教程 10-20
- JAVA获取jvm和操作系统相关信息方法 10-20
- BeanFactory和FactoryBean的区别讲解 10-20
- 微信小程序的宿主环境实现教程 10-10
- dispatchEvent解决重叠元素响应事件教程 10-10