[toc]
1.起因
作为一名从C++转到Java的程序员，我仍然沉迷于C++ STL的各种便捷工具，特别是对于迭代器的灵活运用，我觉得是JDK所比不上的。
最近刷全排列相关的LeetCode题（公司考核所迫），突然想到C++的STL中有提供全排列的库函数，Java有没有？搜了下是没有的，于是我想我能不能实现一个？
1.1 C++ STL中next_permutation的使用
next_permutation算法接受一个序列，在原空间上构造这个序列的“下一个排列组合”，并返回true。当该序列不存在下一个组合时，算法返回false
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
string a = "abc";
cout << a << ' ';
while (next_permutation(a.begin(), a.end())) {
cout << a << ' ';
} // 得到abc acb bac bca cab cba
}
很便捷是吧！在你还在深度优先遍历算法怎么迭代、回退实现全排列的时候，C++程序员已经提交代码了！（当然，我不是鼓励投机取巧哈，DFS还是要掌握的）
1.2 next_permutation原理
第一次接触到next_permutation的原理，是在侯捷老师的《STL源码解析》的书里，这本书看完我大受裨益，非常可惜Java没有这种深入浅出的入门级源码解析著作。
next_permutation的实现思路很巧妙：
- 对于一个序列，从尾端开始往前遍历每一对相邻的两个元素 *i 和 *ii，找到第一对满足 *i < *ii 的相邻元素；
- 再从尾端开始往前找到第一个大于 *i 的元素，令其为 *j；
- 对调 *i 和 *j，最后再将 *ii 之后的所有元素逆序。便得到下一个排列组合。
来看看侯捷老师的描述：
image.png
以下是STL中的next_permutation源码实现（经过侯捷老师美化变量名的版本，便于阅读）：
image.png
2 Java版本的next_permutation实现
讲完了背景，下面上干货，下面是我对STL next_permutation的Java实现版，使用到了模板。要注意的是，由于Java的迭代器不如C++的灵活，实现原理也不同，我没有用Java的迭代器来实现。
package permutation;
import java.util.*;
public class permutation<T extends Comparable> {
public boolean next_permutation(List<T> list) {
if (list == null || list.size() < 2) {
return false;
}
// 从尾端开始找到第一对相邻元素left和right，满足left < right
int left = list.size() - 1;
for (; ; ) {
int right = left;
left--;
if (list.get(left).compareTo(list.get(right)) < 0) {
// 找到满足条件的这对元素后，从尾端开始往前找到第一个比left大的数，将其与left交换
int last = list.size() - 1;
while (list.get(left).compareTo(list.get(last)) >= 0) {
last--;
}
Collections.swap(list, left, last);
// 将right之后的所有元素逆序
Collections.reverse(list.subList(right, list.size()));
return true;
}
// 若找至第一个元素了，把整个list逆序
if (left == 0) {
Collections.reverse(list);
return false;
}
}
}
}
使用方法为：
注意！对于不是升序的序列，要先排序，再使用
package permutation;
import org.junit.Test;
import java.util.*;
public class permutation<T extends Comparable> {
public boolean next_permutation(List<T> list) {
// 省略实现
}
@Test
public void testFunc() {
// 输出：
// [1, 2, 3]
// [1, 3, 2]
// [2, 1, 3]
// [2, 3, 1]
// [3, 1, 2]
// [3, 2, 1]
List<Integer> list = new ArrayList<>(Arrays.asList(new Integer[] {1,2,3}));
System.out.println(list);
while (new permutation<Integer>().next_permutation(list)) {
System.out.println(list);
}
// 输出：
// [a, b, c]
// [a, c, b]
// [b, a, c]
// [b, c, a]
// [c, a, b]
// [c, b, a]
String str = "abc";
List<String> strList = Arrays.asList(str.split(""));
System.out.println(strList);
while (new permutation<String>().next_permutation(strList)) {
System.out.println(strList.toString());
}
}
}
若不想为了使用这个方法而单独定义一个permutation类，可以使用模板函数的形式，直接把下面的方法复制到你的类里：
public <T extends Comparable> boolean next_permutation(List<T> list) {
if (list == null || list.size() < 2) {
return false;
}
// 从尾端开始找到第一对相邻元素left和right，满足left < right
int left = list.size() - 1;
for (; ; ) {
int right = left;
left--;
if (list.get(left).compareTo(list.get(right)) < 0) {
// 找到满足条件的这对元素后，从尾端开始往前找到第一个比left大的数，将其与left交换
int last = list.size() - 1;
while (list.get(left).compareTo(list.get(last)) >= 0) {
last--;
}
Collections.swap(list, left, last);
// 将right之后的所有元素逆序
Collections.reverse(list.subList(right, list.size()));
return true;
}
// 若找至第一个元素了，把整个list逆序
if (left == 0) {
Collections.reverse(list);
return false;
}
}
}
完
