全排列问题。经常使用的排列生成算法有序数法、字典序法、换位法(Johnson(Johnson-Trotter)、轮转法以及Shift cursor cursor* (Gao & Wang)法。
【题目】
Given a collection of numbers, return all possible permutations.
For example,[1,2,3] have the following permutations:[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2],
and [3,2,1].
【暴力递归】
这是比較直观的思路。可是也有要注意的地方。刚開始写的时候，没有注意到list是共用的。所曾经面得到的答案后面会改掉而导致错误。
public class Solution {
List<List<Integer>> ret = new ArrayList<List<Integer>>();
public List<List<Integer>> permute(int[] num) {
int len = num.length;
if (len == 0) return ret;
List<Integer> list = new ArrayList<Integer>();
run(list, num);
return ret;
}
public void run(List<Integer> list, int[] num) {
if (list.size() == num.length) {
//注意这里要又一次new一个list。要不然后面会被改动
List<Integer> res = new ArrayList<Integer>();
res.addAll(list);
ret.add(res);
return;
}
for (int i = 0; i < num.length; i++) {
if (list.contains(num[i])) {
continue;
}
list.add(num[i]);
run(list, num);
list.remove(list.indexOf(num[i])); //不要忘记这一步
}
}
}
【字典序法】
C++的STL库里面有nextPermutation()方法。事实上现就是字典序法。
下图简单明了地介绍了字典序法
归纳一下为：
比如，1234的全排列例如以下：
watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvbGppYWJpbg==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast" alt="">
【代码实现】
因为Java的list传參传的是地址，所以每次加入时都要记得又一次new一个新的list加入到结果集中。否则加入到结果集中的原list会被后面的操作改变。
public class Solution {
public List<List<Integer>> permute(int[] num) {
List<List<Integer>> ret = new ArrayList<List<Integer>>();
int len = num.length;
if (len == 0) return ret;
Arrays.sort(num); //字典序法需先对数组升序排序
//数组转为list
List<Integer> list0 = new ArrayList<Integer>();
for (int i = 0; i < len; i++) {
list0.add(num[i]);
}
//把原始数组相应的list加入到结果中。不能直接加入list0，由于后面它会一直变化
List<Integer> ll = new ArrayList<Integer>();
ll.addAll(list0);
ret.add(ll);
//逐次找下一个排列
for (int i = 1; i < factorial(len); i++) {
ret.add(nextPermutation(list0));
}
return ret;
}
/***字典序法生成下一个排列***/
public List<Integer> nextPermutation(List<Integer> num) {
//找到最后一个正序
int i = num.size()-1;
while(i > 0 && num.get(i-1) >= num.get(i)){
i--;
}
//找到最后一个比num[i-1]大的数
int j = i;
while(j < num.size() && num.get(j) > num.get(i-1)) {
j++;
}
//交换num[i-1]和num[j-1]
int tmp = num.get(i - 1);
num.set(i - 1, num.get(j - 1));
num.set(j - 1, tmp);
//反转i以后的数
reverse(num, i, num.size()-1);
List<Integer> ret = new ArrayList<Integer>();
ret.addAll(num);
return ret;
}
public void reverse(List<Integer> list, int begin, int end) {
for(int i = begin, j = end; i < j; i++) {
list.add(i, list.remove(j));
}
}
public int factorial(int n) {
return (n == 1 || n == 0) ? 1 : factorial(n - 1) * n;
}
}
上面的实现须要先对原数组升序排序。以下对nextPermutation(List<Integer> num)改进后就不用对num排序了。
/***字典序法生成下一个排列***/
public List<Integer> nextPermutation(List<Integer> num) {
//找到最后一个正序
int i = num.size()-1;
while(i > 0 && num.get(i-1) >= num.get(i)){
i--;
} //有了这个推断就不用num最初是按升序排好的了
if (i == 0) {
reverse(num, 0, num.size()-1);
List<Integer> ret = new ArrayList<Integer>();
ret.addAll(num);
return ret;
} //找到最后一个比num[i-1]大的数
int j = i;
while(j < num.size() && num.get(j) > num.get(i-1)) {
j++;
} //交换num[i-1]和num[j-1]
int tmp = num.get(i - 1);
num.set(i - 1, num.get(j - 1));
num.set(j - 1, tmp); //反转i以后的数
reverse(num, i, num.size()-1); List<Integer> ret = new ArrayList<Integer>();
ret.addAll(num);
return ret;
}
欢迎高人对上述代码继续优化！
相关题目：【LeetCode】Next Permutation 解题报告 和 【LeetCode】Permutations II 解题报告