题目描述
输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
输入描述:
<pre>输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。</pre>
这个问题可以进行分解，例如输入abc，求整个字符串的排列可以分解成两步：
1、求出第一个字符的所有可能性，即将第一个字符与其他全部字符交换逐一交换位置。例如可以得到abc、bac、cba。
2、固定第一个字符，对之后的字符重复第一步。abc，bac，cba可以得到abc、acb、bac、bca、cba、cab。
可以通过循环或者递归来实现
解法一：
public class Solution {
public ArrayList<String> Permutation(String str) {
ArrayList<String> res = new ArrayList<String>();
if(str == null || str.length() == 0)
return res;
Queue<String> q = new LinkedList<String>();
q.add(str);
//遍历字符串str，从头到尾依次来确定所有可能情况
for(int index = 0; index < str.length() - 1; index++) {
//使用count来记录已知情况的个数，而不是直接使用q.size(),避免了死循环
int count = q.size();
//遍历res中的所有已知的组合情况
for(int i = 0; i < count; i++) {
char[] s = q.poll().toCharArray();
//将index之后的每个字符与index交换位置，求得所有可能情况
for(int j = index; j < s.length; j++) {
char tmp = s[index];
s[index] = s[j];
s[j] = tmp;
if(!q.contains(String.valueOf(s))){
q.add(String.valueOf(s));
}
}
}
}
for(String s : q) {
res.add(s);
}
Collections.sort(res);
return res;
}
}
上述算法通过循环，依次固定了从0到str.length-1位，从而求得了所有可能。
以str=abc为例：
1、先在res中输入abc
2、确定第一位，在res中删除abc，添加abc、bac、cba。
3、固定第一位，确定第二位，从res中删除abc，添加abc、acb；从res中删除bac，添加bac、bca；从res中删除cba，添加cba、cab。
4、固定第二位，由于第三位只有一种可能，无需确定。对res进行排序，得到字典序结果。
解法二：
public class Solution {
public ArrayList<String> Permutation(String str) {
ArrayList<String> res = new ArrayList<>();
if(str != null && str.length() > 0) {
char[] s = str.toCharArray();
transfer(s, res, 0);
Collections.sort(res);
}
return res;
}
//固定第start位，获得所有可能情况
public void transfer (char[] s, ArrayList<String> res, int start) {
if(start == s.length - 1) {
String val = String.valueOf(s);
if(!res.contains(val)) {
res.add(val);
}
}
else {
for(int i = start; i < s.length; i++) {
//交换
swap(s, start, i);
transfer(s, res, start + 1);
//复位
swap(s, start, i);
}
}
}
//交换函数
public void swap(char[] s, int i, int j) {
char tmp = s[i];
s[i] = s[j];
s[j] = tmp;
}
}
上述代码用递归实现了整个过程，但需要注意的是用于复位的代码
swap(s, start, i);
这行代码容易产生误解，误以为递归出栈后的数组仍为原数组，所以可以直接使用交换函数复位。我们知道，java中虽然都为值传递，但非基本类型作为参数传入时，例如传入数组s时，传入的实际上是引用s的引用，即引用的引用，对形参的修改会影响原数据，所以实际上数组s的值是会改变的。详见文章“Java中对象引用”。
//交换
swap(s, start, i);
transfer(s, res, start + 1);
//复位
swap(s, start, i);
那么问题来了，既然数组s会改变，即使递归出栈得到的也是改变后的数组，紧跟在transfer后的swap得到的数组难道是除了start位以外之后的字符顺序都被打乱的数组？那么为何swap函数又确实起到了复位的作用呢？
答案是因为当递归到最后一层时，swap只能对数组的最后两位进行操作，即i=str.length，假设现在数组为……ab，所以在这一层第二个swap函数确实实现了复位功能，进而递归回退到倒数第二层，由于在上一层将ab位置复位了，即这一层start位之后的ba是原顺序，所以swap函数对……cba也能实现复位。（因为start位c是固定的，只要ba是原顺序，则cba也必为原顺序）。所以这个复位操作是通过递推一步步回退来实现的。
解法三：
使用字典序全排列生成算法来计算。
算法介绍：
假设存在一个全排列P1P2P3P4……Pj-1PjPj+1……Pk-1PkPk+1……Pn-1Pn
我们可以求得其下一个排列。（所谓下一个排列，大于该全排列的最小排列，比如123456的下一个排列是123465）。
步骤为：
1、求得j，其中j=max{i|Pi < Pi-1}，即从左往右第一个开始变小的值得下标。
2、求得k，期中k=max{i|Pi>Pj}，即j的右边大于Pj的值中最大的下标。
3、交换Pj和Pk。
4、将下标从j+1到n的序列翻转。
举例说明：
123465
求得j=3，进而得到k=5，进行交换得到123564，进行翻转，得到123546，所以123465的下一个排列为123546。
这种方法被写在了C++ STL库中。
于是通过循环我们可以很轻松得到全部的字典序排列，只要输入的是最小的字典序排列即可。
