johnson-trotter算法1234

时间: 2023-04-24 15:00:37 浏览: 572

Johnson-Trotter算法实现生成排列

Johnson-Trotter 算法实现生成排列 Johnson-Trotter 算法是生成排列的一种高效算法，通过该算法可以生成 n 个元素的所有排列。该算法的思想是将问题规模减小到 n-1，然后将 n 插入到 n-1 个元素的每种排列中的 n 个可能位置中去，来得到较大规模问题的解。算法思路： 1. 初始化所有移动方向向左 2. 如果移动方向的值比自己小，就可移动 3. 移动最大的可移动项 4. 将所有比移动项大的项方向反转 5. 重复第三步直到不能移动为止代码实现： ```java import java.util.Scanner; public class Permutation { static void generatePermutation(int n) { int a[][] = new int[n][2]; int index; for (int i = 0; i < n; i++) { a[i][0] = i + 1; a[i][1] = 0; // “0”代表箭头向左，“1”代表箭头向右 System.out.print(a[i][0] + " "); } System.out.println(""); for (int i = n; i > 0;) { index = 0; while (a[index][0] != i) index++; if (a[index][1] == 0 && (index - 1) >= 0 && a[index - 1][0] <= a[index][0]) { // 当 i 的箭头方向为 0，指向左边，而且左边存在比 i 小的数， // 则移动，交换它们的位置，各自的箭头方向不变 int temp0 = a[index - 1][0]; int temp1 = a[index - 1][1]; a[index - 1][0] = a[index][0]; a[index - 1][1] = a[index][1]; a[index][0] = temp0; a[index][1] = temp1; for (int j = 0; j < n; j++) { System.out.print(a[j][0] + " "); if (a[j][0] > i) { // 如果输出的数比 i 大，则改变它的箭头方向 if (a[j][1] == 0) a[j][1] = 1; else a[j][1] = 0; } } System.out.println(""); i = n; } else if (a[index][1] == 1 && (index + 1) < n && a[index + 1][0] <= a[index][0]) { // 当 i 的箭头方向为 1，指向右边时，步骤类似箭头指向左边 int temp0 = a[index][0]; int temp1 = a[index][1]; a[index][0] = a[index + 1][0]; a[index][1] = a[index + 1][1]; a[index + 1][0] = temp0; a[index + 1][1] = temp1; for (int j = 0; j < n; j++) { System.out.print(a[j][0] + " "); if (a[j][0] > i) { // 如果输出的数比 i 大，则改变它的箭头方向 if (a[j][1] == 0) a[j][1] = 1; else a[j][1] = 0; } } System.out.println(""); i = n; } else i--; } } } ``` 在上面的代码中，我们使用了一个二维数组 `a` 来存储每个元素的值和箭头方向。在生成排列的过程中，我们使用索引 `index` 来定位要判断的数，然后根据箭头方向和元素值来决定是否移动和交换元素。我们输出生成的排列并改变箭头方向。 Johnson-Trotter 算法是一种高效的生成排列算法，通过将问题规模减小到 n-1，然后将 n 插入到 n-1 个元素的每种排列中的 n 个可能位置中去，来得到较大规模问题的解。

Johnson-Trotter算法是一种用于生成全排列的算法。它的基本思想是通过交换相邻的元素来生成排列。在该算法中，每个排列都有一个方向，即从左到右或从右到左。该算法的主要优点是它可以在不使用递归的情况下生成排列，因此可以避免递归带来的性能问题。1234是一个四个元素的排列，可以使用Johnson-Trotter算法生成所有可能的排列。

阅读全文

johnson-trotter算法1234

相关推荐

johnson-trotter:Johnson-Trotter 置换算法的实现

johnson算法

算法笔记1234

johnson-trotter算法C++实现

permutation-way:置换算法与 Steinhaus-Johnson-Trotter 算法与 Even 加速

Johnson-Trotter算法实现与Java代码详解

使用下面的方法使用c语言编写代码生成{1,2,3,4}的全部排列:Johnson-Trotter算法。

java旅行商问题Johson-Trotter算法数学原理

johnson trotter算法表示c语言

Loopless-Functional-Algorithms:无循环功能算法（Haskell）

组合生成算法

算法作业内容要求

组合数学中的全排列生成算法

组合数学全排列算法（转）

【问题描述】给定正整数n生成1到n的全排列（利用Johnson Trotter算法） 【输入形式】一个整数n（1<=n<=9） 【输出形式】n!行，每一行的第一个数是第几个全排列，第二个数是全排列打印 3 【样例输入】 1123 2132 3312 4321 5231 6213

数据库基础测验20241113.doc

微信小程序下拉选择组件

最新推荐

数据库基础测验20241113.doc

微信小程序下拉选择组件

DICOM文件+DX放射平片-数字X射线图像DICOM测试文件

Jupyter Notebook《基于双流 Faster R-CNN 网络的 图像篡改检测》+项目源码+文档说明+代码注释

使用epf捕获没有CA证书的SSLTLS明文（LinuxAndroid内核支持amd64arm64）.zip

黑板风格计算机毕业答辩PPT模板下载

管理建模和仿真的文件

提升点阵式液晶显示屏效率技术

在SoC芯片的射频测试中，ATE设备通常如何执行系统级测试以保证芯片量产的质量和性能一致？

CodeSandbox实现ListView快速创建指南

【问题描述】给定正整数n生成1到n的全排列（利用Johnson Trotter算法）【输入形式】一个整数n（1<=n<=9）【输出形式】n!行，每一行的第一个数是第几个全排列，第二个数是全排列打印 3 【样例输入】 1123 2132 3312 4321 5231 6213

Jupyter Notebook《基于双流 Faster R-CNN 网络的图像篡改检测》+项目源码+文档说明+代码注释