Java全排列递归算法
2024-09-03 12:36:33
Java全排列算法:
第一遍循环:将list数组index==0的元素依次与数组的每个元素交换,从而保证index==0的位置先后出现n个不同元素之一,实现对index==0位置的遍历。
第 i 遍循环:通过交换, 使index==i的元素,依次与index 为[ i, length-1] 的元素交换。使index==i 位置遍历 length-i 个不同值
第k 次遍历,实质上都是让子列表[ k, length - 1] 的index==0 的位置依次出现length - k 个不同的值,并在出现每个不同的值时,递归操作子列表[ k+1, length - 1]
public class Permutation { public static void permulation(int[] list, int start, int length) {
int i;
if (start == length) {
for (i = 0; i < length; i++)
System.out.print(list[i] + " ");
System.out.println();
} else {
for (i = start; i < length; i++) {
swap(list, start, i);
permulation(list, start + 1, length);
swap(list, start, i);
}
}
} public static void swap(int[] list, int start, int i) {
int temp;
temp = list[start];
list[start] = list[i];
list[i] = temp;
} public static void main(String[] args) {
int length = 3;
int start = 0;
int list[] = new int[length];
for (int j = 0; j < length; j++)
list[j] = j + 1;
permulation(list, start, length);
} }
没有注释,其实因为我觉得注释也不太好写。以list[3]={1,2,3}为例。
一、先是123,然后1与1自己对换,递归排列23,2与2自己对换,递归排列3,然后3与3对换,再递归时满足start==length,即越界,所以把123打印出来;
然后上一步2与2自己对换后,2与3对换,(暂时是132),递归到2与2对换,再递归满足start==length,打印132;
二、最先一步1与1自己对换后,1与2对换,(暂时是213),递归排列13,1与1自己对换,递归排列3. 3与3自己对换,然后满足If条件打印213:
然后退一步,1与3对换,(暂时是231),递归到1与1自己对换,再递归满足打印条件,打印231;
三、1与1、2对换后,1最后与3对换,(暂时是321),递归排列21,2与2对换,递归排列1.1与1自己对换,后来满足打印条件打印321. 2再与1对换,再递归到2与2自己对换,后来打印出312.
写得比较抽象,但只能这样了。只可意会,不可言传~
最新文章
- dll导入导出宏定义,出现“不允许 dllimport 函数 的定义”的问题分析
- CentOS 6.5 Nginx 配置
- java基础-泛型1
- 实现两个MySQL数据库之间的主从同步
- 容器--EnumMap
- php之thinkphp部署Linux
- ue4 SNew补遗
- Lotus中关于字符串处理的函数汇总
- Linux录屏软件
- Google Code Pretiffy 代码 着色 高亮 开源 javascript(JS)库
- EF如何正确的进行实体中修改
- VC常用数据类型使用转换
- PARTITION BY 和 group by
- JS控制台打印星星,总有你要的那一款~
- ubuntu14简介/安装/菜鸟使用手册
- 【慕课网实战】Spark Streaming实时流处理项目实战笔记六之铭文升级版
- 【BZOJ3238】 [Ahoi2013]差异(SAM)
- gridview根据条件来改变行的颜色以及改变单元格的颜色。
- study mysql
- Jurassic.ScriptEngine 使用