全排列输出（递归实现）
全排列是一种比较常用的算法。本文给出递归实现的两个方法。
一、方法一
1.1 思想
处理递归的时候，采用两个字符串变量，一个存放固定前缀，一个 存放剩下的待处理的字符串。如：
@param prefix 固定前缀@param valueToProcess 待处理的字符串固定前缀prefix的初始值为空值“”，随着递归的进行不断变化； 剩下的待处理元素，会随着递归的进行不断减少。
何时输出一个结果？
当剩下的待处理的字符串只有一个元素的时候，直接输出其中一个结果。 格式为：固定前缀 + 待处理的一个元素
private void permuteRecusion(String prefix, String valueToProcess) { int len = valueToProcess.length(); if (len == 1) { System.out.println(prefix + valueToProcess); return; } //省略其余部分 }- 依次从剩下待处理字符元素中，选择一个元素（比如A）与固定前缀组成一个新的固定前缀，然后与新的不包含选中元素（比如A）的待处理字符串元素一道，继续调用递归函数。
- 直到剩下的待处理元素只有一个元素时，将固定前缀和该唯一待处理的元素一道输出。
举个例子，假设要输出ABC的全排列，采用上述思想，输出全排列的过程如下：
- 第一步：
待处理的字符串为ABC， 固定前缀为空 ""
依次从ABC中选取元素，然后与前缀组成新的前缀，有如下三种情况：
A BC , B AC , C AB （注：绿色背景的为固定前缀，黄色背景的待处理的字符串元素）
- 第二步：
第一步中的三个结果，继续调用递归函数，以A BC 为例，
依次从BC中选取元素，然后与前缀（A）组成新的前缀，有如下两种情况：
A BC , A CB
同理，我们可以获取B AC 和C AB 的结果，与A BC 的结果一共产生六个结果，包括：
A BC , A CB B AC , B CA C AB , C BA
- 第三步：
第二步产生的六个结果，继续进行。因为剩下的待处理的字符串元素只有一个，所以直接输出即可。格式为固定前缀+待处理的字符串元素。也就得到ABC的全排列结果：
ABCACBBACBCACABCBA根据上述思想，我们就能很容易地写出递归方法了，如：
/** * @author wangmengjun * */public class Permutation {
/** * 根据指定的字符串，输入全排列 * * @param value * 用于全排列的指定字符串 */ public void permutation(String value) { if (null == value || value.length() == 0) { throw new IllegalArgumentException("value不能为空"); } permuteRecusion("", value); }
/** * 递归处理 * * @param prefix 固定前缀 * @param valueToProcess 待处理的字符串 */ private void permuteRecusion(String prefix, String valueToProcess) { int len = valueToProcess.length(); if (len == 1) { System.out.println(prefix + valueToProcess); return; } for (int i = 0; i < len; i++) { permuteRecusion(prefix + valueToProcess.charAt(i), valueToProcess.substring(0, i) + valueToProcess.substring(i + 1, len)); } } }测试代码
/** * @author wangmengjun * */public class Main {
public static void main(String[] args) { Permutation example = new Permutation(); System.out.println("AB的全排列:"); example.permutation("AB"); System.out.println("ABC的全排列:"); example.permutation("ABC"); }
}输出结果
AB的全排列:ABBAABC的全排列:ABCACBBACBCACABCBA1.2 代码调整
在上述递归代码中，从待处理字符串元素中选出一个元素和固定前缀时，为了得到不包含该选中元素的新的待处理字符串元素，代码采用了字符串substring方法来做。
valueToProcess.substring(0, i) + valueToProcess.substring(i + 1, len)在递归中，上述substring太过频繁，不喜欢。我们写一个新的函数，效果与上述substring操作等效。代码如下：
/** * 返回一个不包含指定下标元素的字符串 * @param i 需要移除元素的下标 * @param valueToProcess 用于处理的字符串 * @return */ private String populateCandidateValue(int i, String valueToProcess) { int len = valueToProcess.length(); char[] sourceValue = valueToProcess.toCharArray(); char[] destValue = new char[len - 1]; System.arraycopy(sourceValue, 0, destValue, 0, i); System.arraycopy(sourceValue, i + 1, destValue, i, destValue.length - i); return new String(destValue);
}将permuteRecusion方法中的substring代码段替换掉。
/** * 递归处理 * * @param prefix 固定前缀 * @param valueToProcess 待处理的字符串 */ private void permuteRecusion(String prefix, String valueToProcess) { int len = valueToProcess.length(); if (len == 1) { System.out.println(prefix + valueToProcess); return; } for (int i = 0; i < len; i++) { permuteRecusion(prefix + valueToProcess.charAt(i), populateCandidateValue(i, valueToProcess)); } }将上述改动，存放在一个新的文件Permutation2.java中。
/** * @author wangmengjun * */public class Permutation2 {
/** * 根据指定的字符串，输入全排列 * * @param value * 用于全排列的指定字符串 */ public void permutation(String value) { if (null == value || value.length() == 0) { throw new IllegalArgumentException("value不能为空"); } permuteRecusion("", value); }
/** * 递归处理 * * @param prefix 固定前缀 * @param valueToProcess 待处理的字符串 */ private void permuteRecusion(String prefix, String valueToProcess) { int len = valueToProcess.length(); if (len == 1) { System.out.println(prefix + valueToProcess); return; } for (int i = 0; i < len; i++) { permuteRecusion(prefix + valueToProcess.charAt(i), populateCandidateValue(i, valueToProcess)); } }
/** * 返回一个不包含指定下标元素的字符串 * @param i 需要移除元素的下标 * @param valueToProcess 用于处理的字符串 * @return */ private String populateCandidateValue(int i, String valueToProcess) { int len = valueToProcess.length(); char[] sourceValue = valueToProcess.toCharArray(); char[] destValue = new char[len - 1]; System.arraycopy(sourceValue, 0, destValue, 0, i); System.arraycopy(sourceValue, i + 1, destValue, i, destValue.length - i); return new String(destValue);
}
}在Permutation2.java中，我们增加了一个函数，用于返回一个不包含指定下标元素的字符串。在这个方法中，我们先将源字符串转换成char数组，然后通过数组复制，返回时，又将目标char数组，转换成String来处理。 还是不喜欢，直接使用char[]数组不就可以了吗？
接下来，我们再来做一些调整，将待处理的字符串，从String改成char[]。修改后的代码如下，存放在Permutation3.java中，
/** * @author wangmengjun * */public class Permutation3 {
/** * 根据指定的字符串，输入全排列 * * @param value * 用于全排列的指定字符串 */ public void permutation(String value) { if (null == value || value.length() == 0) { throw new IllegalArgumentException("value不能为空"); } permuteRecusion("", value.toCharArray()); }
/** * 递归处理 * * @param prefix 固定前缀 * @param valueToProcess 待处理的字符串 */ private void permuteRecusion(String prefix, char[] valueToProcess) { int len = valueToProcess.length; if (len == 1) { System.out.println(prefix + valueToProcess[0]); return; } for (int i = 0; i < len; i++) { permuteRecusion(prefix + valueToProcess[i], populateCandidateValue(i, valueToProcess)); } }
/** * 返回一个不包含指定下标元素的字符串 * @param i 需要移除元素的下标 * @param valueToProcess 用于处理的字符串 * @return */ private char[] populateCandidateValue(int i, char[] sourceValue) { int len = sourceValue.length; char[] destValue = new char[len - 1]; System.arraycopy(sourceValue, 0, destValue, 0, i); System.arraycopy(sourceValue, i + 1, destValue, i, destValue.length - i); return destValue;
}
}至此，方法一的实现就全部结束了。
二、方法二（采用交换的算法）
2.1 思想
方法二的思想是采用交换的算法，思想来源于GeeksforGeeks.org. 网站
ABC全排列的过程如下图所示：
根据上述思想，编写代码如下：
/** * * @author wangmengjun * */public class Permute {
public void permute(String value) { if (StringUtils.isEmpty(value)) { throw new IllegalArgumentException("内容不能为空"); }
int len = value.length(); permuteRecusion(value.toCharArray(), 0, len - 1); }
private void permuteRecusion(char[] charValues, int begin, int end) { if (begin == end) { System.out.println(Arrays.toString(charValues)); return; } for (int i = begin; i <= end; i++) { swap(charValues, begin, i); permuteRecusion(charValues, begin + 1, end); swap(charValues, begin, i); } }
private void swap(char[] charValues, int i, int j) { char temp = charValues[i]; charValues[i] = charValues[j]; charValues[j] = temp; }}三、小结
本篇博文给出了两个递归实现全排列输出的方法。其中，
方法一给出了思想，代码实现、以及对代码的部分优化，也算是一个不错的编写代码的旅程。
方法二，如大家有兴趣，可以参考上述给出的连接，查看更详细的内容。在
本篇博文中就不详细展开讲了，有思路了，编写代码就简单了。
方法二中，使用交换的思想，维持一个char数组，其他通过变换来做。相对方法一，减少了很多数组拷贝或者String对象创建等，相比方法一来讲更好。方法一的优势在于比较好理解。
注：如上两种方法适合没有重复元素的结果，如果有重复元素，还得添加额外的判断条件进行过滤。
全排列输出递归实现就写到这里，后期会找时间将非递归的实现写上去。
如大家有较好的方法，也请告诉我一下，相互交流、相互进步~~~