全排列问题:这是描述数字的全部排列结果的一类问题。有时候经常参杂着一些限制条件。比如12345的全排列,其中34不能连着出现等等。本文以简单的全排列为对象,阐述递归的思想。
递归,要有终止条件,然后向终止条件靠就得到结果了。终止条件可以不止一个。
大致过程如下:
if(终止条件1)
dosomething;
if(终止条件2)
dosomething;
else
去向终止条件递归。
本文以简单的整数全排列问题为demo,示范递归思想。取123456去打印全排列。其中带筛条件的全排列指不能34连续出现的全排列。
全排列代码如下:
package rank;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import org.apache.oro.text.regex.MalformedPatternException;
import org.apache.oro.text.regex.PatternCompiler;
import org.apache.oro.text.regex.Pattern;
import org.apache.oro.text.regex.PatternMatcher;
import org.apache.oro.text.regex.Perl5Compiler;
import org.apache.oro.text.regex.Perl5Matcher;
public class RankDemo {
/**
* 统计总共的排序方法
*/
private static int totalMehtod;
/**
* 存放带筛选条件的全排列排列结果的map 其中排列结果存放在char[]中
*/
private static Map<Integer, char[]> resultMap = new HashMap<Integer, char[]>();
public static void main(String[] args) {
List<Integer> demoList = new ArrayList<Integer>();
for (int i = 0; i < 6; i++)
demoList.add(i + 1);
//全排列
rank(demoList, new ArrayList<Integer>());
System.out.println("There are " + totalMehtod
+ " method all in records!");
//带筛选条件的全排列
rankComplex(demoList, new ArrayList<Integer>(), resultMap);
printMap(resultMap);
}
/**
* 全排列方法
*
* @param inputList
* @param operationList
*/
public static void rank(List<Integer> inputList, List<Integer> operationList) {
if (inputList.size() == 0)
return;
if (inputList.size() == 1) {
for (Integer value : operationList)
System.out.print(value + " ");
System.out.println(inputList.get(0) + " ");
totalMehtod++;
} else {
for (int i = 0; i < inputList.size(); i++) {
List<Integer> tempList = new ArrayList<Integer>();
tempList.addAll(inputList);
Integer temp = tempList.remove(i);
List<Integer> operationListTemp = new ArrayList<Integer>();
operationListTemp.addAll(operationList);
operationListTemp.add(temp);
rank(tempList, operationListTemp);
}
}
}
/**
* 带有筛选条件的全排列方法
*
* @param inputList
* @param operationList
* @param resultMap
*/
public static void rankComplex(List<Integer> inputList,
List<Integer> operationList, Map<Integer, char[]> resultMap) {
if (inputList.size() == 0)
return;
if (inputList.size() == 1) {
operationList.add(inputList.get(0));
StringBuilder sb = new StringBuilder();
for (Integer value : operationList)
sb.append(value);
String temp = sb.toString();
if (!checkCharArray(temp)) {
totalMehtod++;
resultMap.put(totalMehtod, temp.toCharArray());
}
} else {
for (int i = 0; i < inputList.size(); i++) {
List<Integer> tempList = new ArrayList<Integer>();
tempList.addAll(inputList);
Integer temp = tempList.remove(i);
List<Integer> operationListTemp = new ArrayList<Integer>();
operationListTemp.addAll(operationList);
operationListTemp.add(temp);
rankComplex(tempList, operationListTemp, resultMap);
}
}
}
/**
* 筛选方法
* 如果指定了pattern 那么按照这个pattern进行筛选,否则直接返回true
* 若有多个筛选条件,则都可以指定在这个checkCharArray中
* @param temp
* @return
*/
private static boolean checkCharArray(String temp) {
PatternCompiler pComplier = new Perl5Compiler();
Pattern p = null;
try {
// 这里假定筛选条件为不能为34连续出现
p = pComplier.compile("34");
} catch (MalformedPatternException e) {
e.printStackTrace();
}
if(p == null)
return true;
PatternMatcher matcher = new Perl5Matcher();
return matcher.contains(temp, p);
}
/**
* 打印全排列结果
*
* @param resultMap
*/
public static void printMap(Map<Integer, char[]> resultMap) {
for (Integer key : resultMap.keySet()) {
char[] temp = resultMap.get(key);
for (int i = 0; i < temp.length; i++)
System.out.print(temp[i] + " ");
System.out.println();
}
System.out.println("There are " + resultMap.size()
+ " method all in records!");
}
}
说明:简单全排列只需要找到终止条件 输入待排输入大小为1,然后打印操作链表中的值和这一个最终值就好了,还可以顺便统计处方法总数。而带筛选条件的全排列则只需要将符合条件的结果筛选保存到map中,然后打印map就好了。这里筛选使用了正则表达式,更多关于正则表达式的知识可以查看 apache 的oro项目,具体链接如下:http://jakarta.apache.org/oro/
分享到:
相关推荐
递归实现元素全排列
递归实现元素全排列
java 递归,abcd全排列,非常简单的。
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
从集合中依次选出每一个元素,作为排列的第一个元素,然后对剩余的元素进行全排列,如此递归处理,从而得到所有元素的全排列。 (2)字典序排列 把升序的排列(当然,也可以实现为降序)作为当前排列开始,然后依次...
这是一个递归完成全排列的算法,使用的是C++进行编程,希望能帮到你~
去重全排列的递归实现 去掉重复数字的 全排列的 递归实现
主要介绍了Java基于递归解决全排列问题算法,结合实例形式分析了Java使用递归算法解决全排列问题的原理与具体实现技巧,需要的朋友可以参考下
山东大学 数据结构实验 全排列 递归练习
递归打印全排列.cpp
全排列递归算法,在VC下调试OK,递归算法简单快捷,大家理解理解
用回溯法递归实现的输出N的全排列 如 123 132 。。。。
计算机算法与分析试验递归调用快速排序 全排列仅供参考
全排列在笔试面试中很热门,因为它难度适中,既可以考察递归实现,又能进一步考察非递归的实现,便于区分出考生的水平。所以在百度和迅雷的校园招聘以及程序员和软件设计师的考试中都考到了,因此本文对全排列作下...
上传之后才发现头文件少了个ctype.h,因为判断非法输入的时候...如果把整个排列当作一个数的话,实际上整个过程是由小到大的过程,找到的后一个排列刚好是比前一个排列大的最小排列,证明很简单,这里就不在赘述了!
全排列-非递归算法(适合动态的新元素加入重新输出全排列-本程序以1到6的数字输出为例)
c语言递归算法实现数列全排列.pdf
全排列的非递归实现。 输入1,2,3,4 得到 [1 2 3 4]..........[4 3 2 1]所有24种排列
用C语言写的一个递归全排列算法,附有较为详细的注释。
C++学的递归的全排列 当n>10 效率会很低 这个请注意