【算法】求{1,2,3}序列的全排列,邻里交换法(Java)

【算法】求{1,2,3}序列的全排列,邻里交换法(Java)

代码如下:

public class Main{static int count;static int a[]= {1,2,3};public static void main(String[] args) {f(a,0);System.out.println(count);}public static void f(int a[],int step) {if(step==a.length-1) {count++;return;}for(int i=step;i<a.length;i++) {{int x=a[i];//交换a[i]=a[step];a[step]=x;}f(a,step+1);{int x=a[i];//还原数据a[i]=a[step];a[step]=x;}}}
}

图解如下:

执行过程如下:这段代码实现了对数组 a 中元素的全排列,并在 count 中记录排列的数量。下面是每一步的具体细节:

  1. 初始状态:

    • a[] = {1, 2, 3}
    • count = 0
  2. 调用 f(a, 0),进入函数 f

    • a[] = {1, 2, 3}
    • step = 0
  3. 进入 for 循环,i = 0

    • 交换 a[0]a[0](实际上没有变化)
    • 进入递归,调用 f(a, 1)
      • a[] = {1, 2, 3}
      • step = 1
  4. 进入 for 循环,i = 1

    • 交换 a[1]a[1](实际上没有变化)
    • 进入递归,调用 f(a, 2)
      • a[] = {1, 2, 3}
      • step = 2
  5. step == a.length - 1 成立,执行 count++

    • count = 1
  6. 返回上一层递归,恢复数组 a 到初始状态:

    • a[] = {1, 2, 3}
  7. 继续 for 循环,i = 2

    • 交换 a[2]a[1],得到 a[] = {1, 3, 2}
    • 进入递归,调用 f(a, 2)
      • a[] = {1, 3, 2}
      • step = 2
  8. step == a.length - 1 成立,执行 count++

    • count = 2
  9. 返回上一层递归,恢复数组 a 到初始状态:

    • a[] = {1, 2, 3}
  10. 返回上一层递归,恢复数组 a 到初始状态:

    • a[] = {1, 2, 3}
  11. 继续 for 循环,i = 1

    • 交换 a[1]a[0],得到 a[] = {2, 1, 3}
    • 进入递归,调用 f(a, 1)
      • a[] = {2, 1, 3}
      • step = 1
  12. 进入 for 循环,i = 1

    • 交换 a[1]a[1](实际上没有变化)
    • 进入递归,调用 f(a, 2)
      • a[] = {2, 1, 3}
      • step = 2
  13. step == a.length - 1 成立,执行 count++

    • count = 3
  14. 返回上一层递归,恢复数组 a 到初始状态:

    • a[] = {2, 1, 3}
  15. 继续 for 循环,i = 2

    • 交换 a[2]a[1],得到 a[] = {2, 3, 1}
    • 进入递归,调用 f(a, 2)
      • a[] = {2, 3, 1}
      • step = 2
  16. step == a.length - 1 成立,执行 count++

    • count = 4
  17. 返回上一层递归,恢复数组 a 到初始状态:

    • a[] = {2, 1, 3}
  18. 返回上一层递归,恢复数组 a 到初始状态:

    • a[] = {1, 2, 3}
  19. 继续 for 循环,i = 2

    • 交换 a[2]a[0],得到 a[] = {3, 2, 1}
    • 进入递归,调用 f(a, 1)
      • a[] = {3, 2, 1}
      • step = 1
  20. 进入 for 循环,i = 1

    • 交换 a[1]a[1](实际上没有变化)
    • 进入递归,调用 f(a, 2)
      • a[] = {3, 2, 1}
      • step = 2
  21. step == a.length - 1 成立,执行 count++

    • count = 5
  22. 返回上一层递归,恢复数组 a 到初始状态:

    • a[] = {3, 2, 1}
  23. 继续 for 循环,i = 2

    • 交换 a[2]a[1](实际上没有变化)
    • 进入递归,调用 f(a, 2)
      • a[] = {3, 2, 1}
      • step = 2
  24. step == a.length - 1 成立,执行 count++

    • count = 6
  25. 返回上一层递归,恢复数组 a 到初始状态:

    • a[] = {3, 2, 1}
  26. 返回上一层递归,恢复数组 a 到初始状态:

    • a[] = {1, 2, 3}
  27. 返回上一层递归,主函数结束。

最终输出 count 的值为 6,表示数组 [1, 2, 3]

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/306330.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

MAC苹果电脑如何使用Homebrew安装iperf3

一、打开mac终端 找到这个终端打开 二、终端输入安装Homebrew命令 Homebrew官网地址&#xff1a;https://brew.sh/ 复制这个命令粘贴到mac的终端窗口&#xff0c;然后按回车键 /bin/bash -c "$(curl -fsSL https://raw.githubusercontent.com/Homebrew/install/HEAD/in…

未来汽车硬件安全的需求(1)

目录 1.概述 2.EVITA 2.1 EVITA HSM 2.2 EVITA保护范围 3.市场变化对车载网络安全的影响 3.1 非侵入式攻击的风险 3.2 量子计算机的蛮力攻击 3.3 整车E/E架构的变化 3.4 网络安全标准和认证 3.5 汽车工业的网络安全措施 4.汽车安全控制器 4.1 TPM2.0 4.2 安全控…

数据分析案例(一):地区收入的PCA主成分分析

练习1 地区收入的PCA主成分分析 0.变量说明 1.导包操作 核心思路&#xff1a;导入基础数据操作库包&#xff0c;PCA、k-means 库包&#xff0c;数据可视化库包 import pandas as pd import numpy as np from sklearn.decomposition import PCA from sklearn.preprocessing i…

Go语言中channel和互斥锁的应用场景

面对一个并发问题,我们的解决方案是使用channel还是互斥锁来实现并不总是很清晰。因为Go提倡使用通信来共享内存,所以一个常见的错误就是总是强制使用channel,不管实际情况如何。但是我们应该把这两种选择作为互补手段。 首先,简单回顾一下Go语言中的channel:channel是一种交…

软件设计师-基础知识科目-算法设计与分析8

八、算法设计与分析&#xff1a; 常见算法&#xff1a; 回溯方法&#xff1a; 用深度优先的探索问题的解空间。应用场景&#xff1a;N皇后问题。&#xff08;背&#xff09; 分支界限法&#xff1a; 用广度优先的探索问题的解空间&#xff0c;采用的是分支界限法算法设计策…

小程序开发SSL证书下载和安装

在开发小程序时&#xff0c;确保数据的安全传输至关重要&#xff0c;而实现这一目标的关键在于正确获取与安装SSL证书。以下详细介绍了从获取到安装SSL证书的完整流程&#xff0c;以助您为小程序构建可靠的加密通信环境。 一、小程序SSL证书类型选择&#xff1a; 域名验证型D…

互联网轻量级框架整合之设计模式

反射技术 Java的反射技术能够通过配置类的全限定名、方法和参数完成对象的初始化&#xff0c;甚至反射某些方法&#xff0c;大大的增强了Java的可配置型&#xff0c;这也是Spring IoC的底层原理&#xff0c;Java的反射技术覆盖面很广&#xff0c;包括对象构建、反射方法、注解、…

备战蓝桥杯---刷杂题2

显然我们直接看前一半&#xff0c;然后我们按照斜行看&#xff0c;我们发现斜行是递增的&#xff0c;而同一行从左向右也是递增的&#xff0c;因此我们可以直接二分&#xff0c;同时我们发现对称轴的数为Ck,2k. 我们从16斜行枚举即可 #include<bits/stdc.h> using name…

YOLOV5训练KITTI数据集实践

目录 一、YOLOV5下载安装二、KITTI数据集三、标签格式转换四、修改配置文件五、训练六、测试 一、YOLOV5下载安装 git clone https://github.com/ultralytics/yolov5.git conda create -n yolov5 python3.8 -y conda activate yolov5 cd yolov5 pip install -r requirements.t…

一文了解ERC404协议

一、ERC404基础讲解 1、什么是ERC404协议 ERC404协议是一种实验性的、混合的ERC20/ERC721实现的&#xff0c;具有原生流动性和碎片化的协议。即该协议可让NFT像代币一样进行拆分交易。是一个图币的互换协议。具有原生流动性和碎片化的协议。 这意味着通过 ERC404 协议&#xf…

gitlab、jenkins安装及使用文档一

gitlab-jenkins安装文档 IP地址操作系统服务版本192.168.75.137Rocky9.2jenkins 2.450-1.1 jdk 11.0.22 git 2.39.3192.168.75.138Rocky9.2gitlab-ce 16.10.0 gitlab安装 前期准备: 关闭防火墙及 SELinuxsystemctl disable --now firewalld sed -i s/^SELINUXenforcing$…

谷歌seo自然搜索排名怎么提升快?

要想在谷歌上排名快速上升&#xff0c;关键在于运用GPC爬虫池跟高低搭配的外链组合 首先你要做的&#xff0c;就是让谷歌的蜘蛛频繁来你的网站&#xff0c;网站需要被谷歌蜘蛛频繁抓取和索引&#xff0c;那这时候GPC爬虫池就能派上用场了&#xff0c;GPC爬虫池能够帮你大幅度提…

短剧小程序系统开发,让短剧观看与创作更加便捷。短剧系统源码搭建

一、目前短剧发展趋势 1. 市场规模&#xff1a;根据数据来看&#xff0c;2023年中国微短剧市场规模达到了373.9亿元&#xff0c;同比上升了267.65%。预计2024年市场规模将超过500亿元。这一市场规模的增长速度非常显著&#xff0c;显示出短剧行业的巨大潜力和发展前景。 2. 投…

RabbitMQ消息模型之Fanout消息模型

Fanout消息模型 * 广播模型&#xff1a;* 一个交换机绑定多个队列* 每个队列都有一个消费者* 每个消费者消费自己队列中的消息&#xff0c;每个队列的信息是一样的生产者 package com.example.demo02.mq.fanout;import com.example.demo02.mq.util.ConnectionUtils; impor…

Python异常处理try与except跳过报错使得程序继续运行的方法

本文介绍基于Python语言的异常处理模块try与except&#xff0c;对代码中出现的报错加以跳过&#xff0c;从而使得程序继续运行的方法。 在Python语言中&#xff0c;try语句块用于包含可能引发异常的代码&#xff0c;而except语句块则用于定义在出现异常时要执行的代码。其基本结…

Windows下编译boost库

官网&#xff1a;https://www.boost.org/ 下载地址&#xff1a;https://github.com/boostorg/boost 这里使用github下载 使用git bash运行bootstrap.sh 运行b2.exe,会生成bin.v2和stage文件夹 Cmake引入

03-JAVA设计模式-适配器模式

适配器模式 设么是适配器模式 它属于结构型模式&#xff0c;主要用于将一个类的接口转换成客户端所期望的另一种接口&#xff0c;从而使得原本由于接口不兼容而无法协同工作的类能够一起工作。 适配器模式主要解决的是不兼容接口的问题。在软件开发中&#xff0c;经常会有这…

前端对接fastGPT流式数据+打字机效果

首先在对接api时 参数要设置stream: true, const data {chatId: abc,stream: true,//这里true返回流式数据detail: false,variables: {uid: sfdsdf,name: zhaoyunyao,},messages: [{ content: text, role: user }]}; 不要用axios发请求 不然处理不了流式数据 我这里使用fetch …

通过Transform与Animation,来探索CSS中的动态视觉效果

在 transform 和 animation 出现之前&#xff0c;前端开发者通常需要编写大量的 JavaScript 代码来实现动态效果。然而&#xff0c;这两个 CSS 属性的引入极大地简化了丰富动效和过渡效果的实现&#xff0c;从而让用户界面更加引人入胜&#xff0c;交互体验更为流畅。本文将深入…

详解Qt添加外部库

在Qt项目中添加外部库是一项常见任务&#xff0c;无论是静态库还是动态库都需要正确的配置才能让项目顺利编译链接。以下是详细步骤和不同场景下的配置方法&#xff1a; 方法一&#xff1a;手动编辑.pro文件 添加头文件路径&#xff1a; 在Qt项目中的.pro文件中使用INCLUDEPAT…