问题描述：
输入一个字符串，打印出该字符串的所有排列。例如，输入字符串”abc”，则输出有字符’a’,’b’,’c’所能排列出来的所有字符串”abc”,”acb”,”bac”,”bca”,”cab”,”cba”。
问题补充：
输入的字符必须是不重复的，否则输出的字符串排列也是有重复的
递归实现:
public class StringArrange {
/*
* 参数arrayA:给定字符串的字符数组
* 参数start:开始遍历字符与其后面各个字符将要进行交换的位置
* 参数end:字符串数组的最后一位
* 函数功能：输出字符串数字的各个字符全排列
*/
public void recursionArrange(char[] arrayA,int start,int end){
if(end <= 1)
return;
//满足最后条件则可以输出，而且输出的是本数组，因为经过了交换，没有辅助数组，所以一个一个输出就可以达到目的
if(start == end){
for(int i = 0;i < arrayA.length;i++)
System.out.print(arrayA[i]);
System.out.println();
}
else{
// for循环依次选取当前数组start至end位置的元素
for(int i = start;i <= end;i++){
// 把索引到的数据元素与第一个元素的位置交换，表示选取了此数据做排列第一个
// 交换的目的就是为了后面更好的递归，不会出现交叉情况，而且不增加额外的空间复杂度
swap(arrayA,i,start);
// 重复此操作依次选择第2,3,...,n位的数据元素排列
recursionArrange(arrayA,start+1,end);
//每交换依次，弄完了记得把数据交换回来，防止后面数据混乱
swap(arrayA,i,start);
}
}
}
//交换数组m位置和n位置上的值
public void swap(char[] arrayA,int m,int n){
char temp = arrayA[m];
arrayA[m] = arrayA[n];
arrayA[n] = temp;
}
public static void main(String[] args){
StringArrange test = new StringArrange();
String A = "abc";
char[] arrayA = A.toCharArray();
test.recursionArrange(arrayA,0,arrayA.length-1);
}
}
其他的处理方法：
字典排序法，可以避免重复情况发生
字典排序问题
输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
代码实现
import java.util.ArrayList;
import java.util.Collections;
public class Solution {
public ArrayList<String> Permutation(String str) {
if (str.length() == 0)
return new ArrayList<String>();
char[] strArr = str.toCharArray();
ArrayList<String> arr = new ArrayList<String>();
int[] alphabet = new int[255]; //想用hash表来实现查重，避免collection容器自带的，但是总是通不过，所以就放弃了
permute(strArr, 0, arr, alphabet);
Collections.sort(arr);
return arr;
}
public void permute(char[] strArr, int start, ArrayList<String> arr, int[] alphabet) {
if (start >= strArr.length - 1) {
//String s = strArr.toString(); 用这句实现，返回的是一个类，则最终输出结果为[C@15db9742
String s = String.valueOf(strArr);//要得到一个字符串的值，必须用valueOf()这个函数
if (!arr.contains(s)) {
arr.add(s);
}
}
for (int i = start; i < strArr.length; ++i) {
// if (alphabet[(int) strArr[i]] == 0) {
// alphabet[(int) strArr[i]] = 1;
swap(strArr, i, start);
permute(strArr, start + 1, arr, alphabet); //这里中间那个数start是自己加1，而不是带入i这个值
swap(strArr, i, start);
// }
}
}
public void swap(char[] strArr, int left, int right) {
char tmp = strArr[left];
strArr[left] = strArr[right];
strArr[right] = tmp;
}
}
参考文献：
[1] 算法笔记_025:字符串的全排列（Java）
[2] 含有重复字符的字符串排列组合
