递归总结一 全排列问题

全排列问题：这是描述数字的全部排列结果的一类问题。有时候经常参杂着一些限制条件。比如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/