全排列递归实现

全排列是一种比较常用的算法。本文给出一个全排列的递归实现方法。

 

首先，我们一起来一下有什么规律可循。

 

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

 

上述的程序适合字符串中无重复的字符，如果有相同的字符，那么就会产生重复结果；

如果需要输出无重复的结果集合，需要再添加重复验证，最简单的就是将每个结果放在Set中去重。