两种常用的全排列算法(java)

2024-03-25 05:55| 来源: 网络整理| 查看: 265

问题：给出一个字符串，输出所有可能的排列。

全排列有多种算法，此处仅介绍常用的两种：字典序法和递归法。

1、字典序法：

如何计算字符串的下一个排列了？来考虑"926520"这个字符串，我们从后向前找第一双相邻的递增数字，"20"、"52"都是非递增的，"26 "即满足要求，称前一个数字2为替换数，替换数的下标称为替换点，再从后面找一个比替换数大的最小数（这个数必然存在），0、2都不行，5可以，将5和2交换得到"956220"，然后再将替换点后的字符串"6220"颠倒即得到"950226"。

算法概括：从后向前遍历，找出第一个交换点，再按照规则找出第二个交换点，将两者进行交换，对第一个交换点之后的字符进行颠倒操作

package algorithm; import java.util.Arrays; public class DictionaryPermutation { private char[] data; private int length; public void permutate(String input) { // change the data type to we needed changeToData(input); // sort the data from small to big Arrays.sort(data); // output all the order System.out.println(data); while (nextPermutate()) { System.out.println(data); } } private void changeToData(String input) { if (input == null) return; data = input.toCharArray(); length = data.length; } private boolean nextPermutate() { int end = length - 1; int swapPoint1 = end, swapPoint2 = end; // the actual swap-point is swapPoint1 - 1 while (swapPoint1 > 0 && data[swapPoint1] 0 && data[swapPoint2]

【本文地址】

公司简介

联系我们