求全排列的两种方法(Java)

2023-10-28 02:30
文章标签 java 方法 两种 排列 求全

本文主要是介绍求全排列的两种方法(Java),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

递归法

假设我们有0,1,2,3四个数需要全排列,递归法是一种比较类似于深度搜索的方法,直到递归最深处,才得出结果。

其大概思路是,设置一个游标start,游标所到之处,其左侧已经考虑过,利用递归思想求剩下的全排列。

仔细分析,依次考虑每一位数。由于对于每一位数,它可能的数包括除了之前考虑过的所有数,因此将start右侧(包括start)的所有数都和start这一位交换一次,每交换后,马上进入递归函数(start+1),接着再执行一次原交换,用于复原。这样就做成了把每一个数都在这个位上排列一次,递归函数的调用表示对剩下的数进行全排列。

代码如下:

package main;public class Main {static int[] a = {0, 1, 2, 3};static int result = 0;public static void main(String[] args) {dfs(0);System.out.println("The total of all permutation of a[] is: " + result);}public static void dfs(int start) {if (start >= a.length) {System.out.print(a[0]);for (int i = 1; i < a.length; i++) {System.out.print(", " + a[i]);}System.out.println();result++;return;}for (int i = start; i < a.length; i++) {swap(start, i);dfs(start + 1);swap(start, i);}}public static void swap(int i, int j) {int temp = a[i];a[i] = a[j];a[j] = temp;}
}

给出输出结果:
在这里插入图片描述

回溯法

这种方法叫回溯法,他的思想也是用到递归的思想,长得也和上面递归法很像,只是从递归函数的解读来说,和递归法还是有区别的。(leetcode上经常有回溯法求解的题)

在回溯法中,通常有多个辅助变量:待选列表或集合,已选列表或集合,表示结果的列表或集合,等等。其递归思想,就是

  1. 每次遍历待选
  2. 更新表示结果的列表或集合
  3. 更新已选列表或集合
  4. 执行递归操作
  5. 恢复表示结果的列表或集合,恢复已选列表或集合。

这么看来,好像是和递归法没什么区别。我的理解是,递归法和回溯法本质上都是递归,在求全排列问题上,递归解法和回溯法极其相似,但是在一些应用问题中,用递归法不是那么好理解,而回溯法的思考模式和我们人想问题差不多,递归套路就是挨个试,因此回溯法还是比较容易接受的。

还有一点要注意的是,在全排列问题上,回溯法用的复杂度较高,效率低于递归法。

下面附上代码:

package main;import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;public class Main {static int[] a = {0, 1, 2, 3};static Set<Integer> all = new HashSet<Integer>(); // 全体集合(待选集合=全体集合-已选集合)static Set<Integer> used = new HashSet<Integer>(); // 已选集合static List<List<Integer>> resultList = new ArrayList<>(); // 全局结果列表public static void main(String[] args) {for (int i = 0; i < a.length; i++) {all.add(a[i]);}backtrack(0, new ArrayList<Integer>());System.out.println("The total of all permutation of a[] is: " + resultList.size());}public static void backtrack(int p, List<Integer> tempresult) {if (p >= a.length) {System.out.print(tempresult.get(0));for (int i = 1; i < tempresult.size(); i++) {System.out.print(", " + tempresult.get(i));}System.out.println();resultList.add(tempresult);return;}for (Integer n : all) {if (!used.contains(n)) {used.add(n);tempresult.add(n);backtrack(p + 1, tempresult);tempresult.remove(tempresult.size() - 1);used.remove(n);}}}public static void swap(int i, int j) {int temp = a[i];a[i] = a[j];a[j] = temp;}
}

执行结果:
在这里插入图片描述

执行结果对比

比较上面两个方法中,输出执行结果的区别,发现:

在递归法中:
在这里插入图片描述
回溯法中:
在这里插入图片描述
由于两种方法(尽管都用到了递归)对递归含义的解释,也就是执行思路不同,导致了结果输出顺序的不同。

在递归法中,先输出0321,后输出0312,是因为此时正在考虑第二位(start=1),已经对这一位考虑过了数字1和数字2,现在需要将数字3和原本的1做交换,而这个操作和数字2无关,所以数字2还在它原来的位置上。直到考虑第三位时(start=2),才与后面的1交换,输出了0321.

在回溯法中,先输出0312,后输出0321,这是因为,在集合的遍历中,由于对集合all的遍历顺序实际上是字典序(数字从小到大),因此这就好比我们人的思维模式,逐位考虑可能的数字,而考虑的顺序就是字典序了。这样最后输出的全排列顺序,也是字典序。

谢谢!

这篇关于求全排列的两种方法(Java)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/290070

相关文章

SpringBoot结合Knife4j进行API分组授权管理配置详解

《SpringBoot结合Knife4j进行API分组授权管理配置详解》在现代的微服务架构中,API文档和授权管理是不可或缺的一部分,本文将介绍如何在SpringBoot应用中集成Knife4j,并进... 目录环境准备配置 Swagger配置 Swagger OpenAPI自定义 Swagger UI 底

解决hive启动时java.net.ConnectException:拒绝连接的问题

《解决hive启动时java.net.ConnectException:拒绝连接的问题》Hadoop集群连接被拒,需检查集群是否启动、关闭防火墙/SELinux、确认安全模式退出,若问题仍存,查看日志... 目录错误发生原因解决方式1.关闭防火墙2.关闭selinux3.启动集群4.检查集群是否正常启动5.

SpringBoot集成EasyExcel实现百万级别的数据导入导出实践指南

《SpringBoot集成EasyExcel实现百万级别的数据导入导出实践指南》本文将基于开源项目springboot-easyexcel-batch进行解析与扩展,手把手教大家如何在SpringBo... 目录项目结构概览核心依赖百万级导出实战场景核心代码效果百万级导入实战场景监听器和Service(核心

idea Maven Springboot多模块项目打包时90%的问题及解决方案

《ideaMavenSpringboot多模块项目打包时90%的问题及解决方案》:本文主要介绍ideaMavenSpringboot多模块项目打包时90%的问题及解决方案,具有很好的参考价值,... 目录1. 前言2. 问题3. 解决办法4. jar 包冲突总结1. 前言之所以写这篇文章是因为在使用Mav

Spring Security6.3.x的使用指南与注意事项

《SpringSecurity6.3.x的使用指南与注意事项》SpringSecurity6.3.1基于现代化架构,提供简洁配置、增强默认安全性和OAuth2.1/OIDC支持,采用Lambda... 目录介绍基础配置 (Servlet 应用 - 使用 Lambda DSL)关键配置详解(Lambda DS

Java Stream 的 Collectors.toMap高级应用与最佳实践

《JavaStream的Collectors.toMap高级应用与最佳实践》文章讲解JavaStreamAPI中Collectors.toMap的使用,涵盖基础语法、键冲突处理、自定义Map... 目录一、基础用法回顾二、处理键冲突三、自定义 Map 实现类型四、处理 null 值五、复杂值类型转换六、处理

SpringBoot实现RSA+AES自动接口解密的实战指南

《SpringBoot实现RSA+AES自动接口解密的实战指南》在当今数据泄露频发的网络环境中,接口安全已成为开发者不可忽视的核心议题,RSA+AES混合加密方案因其安全性高、性能优越而被广泛采用,本... 目录一、项目依赖与环境准备1.1 Maven依赖配置1.2 密钥生成与配置二、加密工具类实现2.1

在Java中实现线程之间的数据共享的几种方式总结

《在Java中实现线程之间的数据共享的几种方式总结》在Java中实现线程间数据共享是并发编程的核心需求,但需要谨慎处理同步问题以避免竞态条件,本文通过代码示例给大家介绍了几种主要实现方式及其最佳实践,... 目录1. 共享变量与同步机制2. 轻量级通信机制3. 线程安全容器4. 线程局部变量(ThreadL

Python清空Word段落样式的三种方法

《Python清空Word段落样式的三种方法》:本文主要介绍如何用python-docx库清空Word段落样式,提供三种方法:设置为Normal样式、清除直接格式、创建新Normal样式,注意需重... 目录方法一:直接设置段落样式为"Normal"方法二:清除所有直接格式设置方法三:创建新的Normal样

在Linux系统上连接GitHub的方法步骤(适用2025年)

《在Linux系统上连接GitHub的方法步骤(适用2025年)》在2025年,使用Linux系统连接GitHub的推荐方式是通过SSH(SecureShell)协议进行身份验证,这种方式不仅安全,还... 目录步骤一:检查并安装 Git步骤二:生成 SSH 密钥步骤三:将 SSH 公钥添加到 github