邻位互换法 由 Johnson-Trotter 首先提出的，算法利用递归思想，将第 n 个数插入到 n-1 阶排列的不同位置，从而得到不同排列。本文将给出算法的原理及 Java 和 Go 语言的代码实现。
下面是求所有排列的一般步骤：
- n = 1：1
- n = 2：12,21
- n = 3：123,132,312；213,231，321
java 实现如下：
1 | public static List<int[]> getAllPermutation(int[] arr) { |
用这种方法我们为了产生任意 n 阶排列，必须先知道所有 n-1 阶排列，因此必须先存储所有 n-1 阶排列才能产生出所有 n 阶排列，如果考虑算法复杂度，这将是一个很大的缺点。通过分析过程，我们可以找到通过邻位交换来产生下一个排列的方式，即邻位交换法。
活动状态： 从初始排列 1234 开始，在每个数上方加一个箭头，<– 表示向左，–> 表示向右，为了书写方便，我们用 L 表示向左，R 表示向右，初始排列方向都向左，如 1( L ),2( L ),3( L ),4( L )。如果一个数箭头所指的方向，相邻的数比这个数小，则称这个数处于活动状态。如排列 1( L ),2( L ),3( L ),4( L ) 中数 2、3、4 都处于活动状态。我们很容易总结出以下特性：
- 最小的数永远不是活动状态
- 第一个数且箭头指向左侧的数永远不是活动状态
- 最后一个数且箭头指向右侧的数永远不是活动状态
根据数列中每个数的活动状态，我们可以找到任一排列 p=p(1)…,p(i-1),p(i),…,p(n) 的下一个排列：
- 若排列中没有处于活动的数，则排列没有下一个排列
- 找到排列中处于活动状态的数中的最大者 p(x)
- 把 p(x) 与它指向的相邻的数互换
- 改变所有比 p(x) 大的数的方向，然后转向第 1 步
下面是算法的 Java 实现供参考：
定义带方向的 int 结构类型 DirectionalInt
class DirectionalInt {
private int value;
private int direction; // 0 向左，1 向右
public DirectionalInt(int value) {
this.value = value;
}
public boolean isLeft() {
return this.direction == 0;
}
public boolean isRight() {
return !isLeft();
}
public void reverse() {
this.direction = this.direction ^ 1;
}
}
交换数组中两个位置的元素
private static void swap(DirectionalInt[] directionalInts, int i, int j) {
DirectionalInt tmp = directionalInts[i];
directionalInts[i] = directionalInts[j];
directionalInts[j] = tmp;
}
产生指定排列的下一个排列
private static DirectionalInt[] nextPermutation(DirectionalInt[] directionalInts) {
int maxActiveIndex = -1;
DirectionalInt maxActive = null;
// 查找最大活动元素及其索引
for (int i = 0; i < directionalInts.length; i++) {
DirectionalInt current = directionalInts[i];
if (current.isLeft() && i > 0) {
DirectionalInt pre = directionalInts[i - 1];
if ((pre.getValue() < current.getValue()) && (maxActive == null || maxActive.getValue() < current.getValue())) {
maxActiveIndex = i;
maxActive = current;
}
}
if (current.isRight() && i < directionalInts.length - 1) {
DirectionalInt next = directionalInts[i + 1];
if ((next.getValue() < current.getValue()) && (maxActive == null || maxActive.getValue() < current.getValue())) {
maxActiveIndex = i;
maxActive = current;
}
}
}
// 如果没有活动元素也就没有下一个排列
if (maxActive == null) {
return null;
}
// 交换最大活动元素与箭头所指相邻元素
if (maxActive.isLeft()) {
swap(directionalInts, maxActiveIndex, maxActiveIndex - 1);
} else if (maxActive.isRight()) {
swap(directionalInts, maxActiveIndex, maxActiveIndex + 1);
}
// 改变所有比最大活动元素大的元素的方向
for (DirectionalInt directionalInt : directionalInts) {
if (directionalInt.getValue() > maxActive.getValue()) {
directionalInt.reverse();
}
}
return directionalInts;
}
由初始排列产生所有排列
public static List<int[]> getAllPermutation(int[] arr) {
List<int[]> result = new ArrayList<>();
result.add(arr);
// 构造带方向的元素数组
DirectionalInt[] directionalInts = Arrays.stream(arr).mapToObj(DirectionalInt::new).toArray(DirectionalInt[]::new);
// 不断产生下一个排列，直到没有下一个
DirectionalInt[] nextDirectionalInts = nextPermutation(directionalInts);
while (nextDirectionalInts != null) {
int[] nextArray = Arrays.stream(nextDirectionalInts).mapToInt(DirectionalInt::getValue).toArray();
result.add(nextArray);
nextDirectionalInts = nextPermutation(nextDirectionalInts);
}
return result;
}
** 源码位置 **
