全排列是一种比较常用的算法。本文给出一个全排列的递归实现方法。
首先,我们一起来一下有什么规律可循。
1. 如果待处理的字符串的长度为1,则直接输出即可。
2. 如果待处理的字符串的长度为2,则有两种情况:
假设字符串为“AB”, 那么直接输出AB 和BA即可。
3. 如果待处理的字符串长度大于2,那么调用递归方法实现。
思想 ==> 在处理递归方法的时候,考虑两个值,一个是固定的前缀值,另一个是剩余的用于全排列的字符串。当剩余的用于全排列的字符串长度为2个或者1个(只有当用于全排列的字符串的长度为1,也即只有一个字符的时候才发生),直接输出结果,格式为固定的前缀+剩余字符的全排列。
有了上述的基本思想,我们就可以很容易写出代码来了,代码如下:
/** * @author wangmengjun * */ public class Permutation { /** * 根据指定的字符串,输入全排列 * * @param value * 用于全排列的指定字符串 */ public void permutation(String value) { if (null == value || value.length() == 0) { throw new IllegalArgumentException("value不能为空"); } permutationResc("", value); } /** * 递归处理 * * @param prefix 固定前缀 * @param valueToProcess 待处理的字符串 */ private void permutationResc(String prefix, String valueToProcess) { int len = valueToProcess.length(); if (len == 1) { System.out.println(prefix + valueToProcess); } else if (len == 2) { /** * 如果待处理的字符串只有2个字符了,那么直接输出这两种情况 System.out.println(prefix * +valueToProcess); 等价于 * System.out.println(prefix+valueToProcess.charAt(0) + * valueToProcess.charAt(1)); */ System.out.println(prefix + valueToProcess); System.out.println(prefix + valueToProcess.charAt(1) + valueToProcess.charAt(0)); } else { for (int i = 0; i < len; i++) permutationResc( prefix + valueToProcess.charAt(i), valueToProcess.substring(0, i) + valueToProcess.substring(i + 1, len)); } } }
public class Main { public static void main(String[] args) { Permutation example = new Permutation(); example.permutation("A"); System.out.println(); example.permutation("AB"); System.out.println(); example.permutation("ABC"); System.out.println(); example.permutation("ABCD"); } }
输出结果:
A AB BA ABC ACB BAC BCA CAB CBA ABCD ABDC ACBD ACDB ADBC ADCB BACD BADC BCAD BCDA BDAC BDCA CABD CADB CBAD CBDA CDAB CDBA DABC DACB DBAC DBCA DCAB DCBA
相关推荐
去重全排列的递归实现 去掉重复数字的 全排列的 递归实现
JAVA递归实现全排列算法,含实现源代码,如a、b、c、d的全排列为: abcd abdc acbd acdb adcb adbc bacd badc bcad bcda bdca bdac cbad cbda cabd cadb cdab cdba dbca dbac dcba dcab dacb dabc
(1)递归实现 从集合中依次选出每一个元素,作为排列的第一个元素,然后对剩余的元素进行全排列,如此递归处理,从而得到所有元素的全排列。 (2)字典序排列 把升序的排列(当然,也可以实现为降序)作为当前排列...
递归实现元素全排列
全排列的非递归实现。 输入1,2,3,4 得到 [1 2 3 4]..........[4 3 2 1]所有24种排列
全排列-基于递归实现
递归实现元素全排列
用回溯法递归实现的输出N的全排列 如 123 132 。。。。
不得不说的全排列算法递归实现 我真的是菜啊,留的算法作业几乎没有一次自己写出来过…都是要上网看别人的博客才能懂,自己好笨好菜,
主要为大家详细介绍了python递归全排列实现方法,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
上传之后才发现头文件少了个ctype.h,因为判断非法输入的时候用到了isalpha(),不加这个头文件的话在gcc下会有警告,在VC下可能编译不过! 首先把输入的各个数由小到大进行排序,然后开始 1.找出比右边数字小的第一...
这是一个递归完成全排列的算法,使用的是C++进行编程,希望能帮到你~
(一)非递归全排列算法基本思想是: 1.找到所有排列中最小的一个排列P. 2.找到刚刚好比P大比其它都小的排列Q, 3.循环执行第二步,直到找到一个最大的排列,算法结束.下面用数学的方法描述:给定已知序列 P = A1A2A3...
使用递归实现的全排列算法,输出所有的全排列。 各种主流程序设计语言实现!
算法原理如果用P表示n个元素的全排列,而Pi表示n个元素中不包含元素i的全排列,(i)Pi表示在排列Pi前面加上前缀i的排列,那么n个元素的全排列可递归定义为: ① 如果n=1,则排列P只有一个元素i; ② 如果n>1,则...
java 递归,abcd全排列,非常简单的。
包含多个经典的递归应用代码: 1.fibonacci.c 是斐波拉契数列递归解法 ...3.permutation.c 是全排列递归算法 4.queen.c 是八皇后递归算法 5. reverse.c 是递归的测试代码 6.strlrn.c 是求字符串长度的递归算法
代码以C++作为编程语言,分别用递归和穷尽法实现全排列。