排列组合算法 - 邻位互换法

邻位互换法 由 Johnson-Trotter 首先提出的，算法利用递归思想，将第 n 个数插入到 n-1 阶排列的不同位置，从而得到不同排列。本文将给出算法的原理及 Java 和 Go 语言的代码实现。

下面是求所有排列的一般步骤：

1. n = 1：1
2. n = 2：12,21
3. n = 3：123,132,312；213,231，321

java 实现如下：

public static List<int[]> getAllPermutation(int[] arr) {
  if (arr.length == 1) {
    return Collections.singletonList(arr);
  }
  // 将原数组拆分成最后一个数和去掉最后一个数的子数组两部分
  int lastValue = arr[arr.length - 1];
  int[] subArr = new int[arr.length - 1];
  System.arraycopy(arr, 0, subArr, 0, arr.length - 1);
  
  // 递归求得数组 subArr 的所有排列
  List<int[]> subArrs = getAllPermutation(subArr);

  List<int[]> list = new ArrayList<>();
  // 将最后一个数每个子排列得到所有排列
  subArrs.forEach(tmpArr -> {
    List<int[]> subList = getPermutations(tmpArr, lastValue);
    list.addAll(subList);
  });

  return list;
}

// 将值 value 依次插入到数组 subArr 的各个位置得到所有由 subArr 和 value 组成的排列
private static List<int[]> getPermutations(int[] subArr, int value) {
  int len = subArr.length + 1;
  List<int[]> list = new ArrayList<>(len);
  for (int i = subArr.length; i >= 0; i--) {
    int[] tmp = new int[len];
    System.arraycopy(subArr, 0, tmp, 0, i);
    tmp[i] = value;
    System.arraycopy(subArr, i, tmp, i + 1, subArr.length - i);
    list.add(tmp);
  }
  return list;
}

用这种方法我们为了产生任意 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 都处于活动状态。我们很容易总结出以下特性：

1. 最小的数永远不是活动状态
2. 第一个数且箭头指向左侧的数永远不是活动状态
3. 最后一个数且箭头指向右侧的数永远不是活动状态

根据数列中每个数的活动状态，我们可以找到任一排列 p=p(1)…,p(i-1),p(i),…,p(n) 的下一个排列：

1. 若排列中没有处于活动的数，则排列没有下一个排列
2. 找到排列中处于活动状态的数中的最大者 p(x)
3. 把 p(x) 与它指向的相邻的数互换
4. 改变所有比 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;
  }

** 源码位置 **

• NeighbourExchangeUtilV1.java
• NeighbourExchangeUtilV2.java
• NeighbourExchangeUtilTest.java
• neighbour_exchange_v1.go
• neighbour_exchange_v1_test.go
• neighbour_exchange_v2.go
• neighbour_exchange_v2_test.go