排列组合算法 - 字典序法

字典序法指对给定的字符集中的字符规定了一个先后关系，在此基础上规定两个全排列的先后是从左到右逐个比较对应的字符的先后。因此对于一个给定的序列，我们只要不断求出其下一个排列，直到其没有下一个（没有任何一个元素后面存在“应该在它前面”的元素）,便可以逐一列举出当前序列的全部排列。

下面给出求任一排列 p=p(1)…,p(i-1),p(i),…,p(n) 的下一个排列的一般步骤：

1. 找到当前排列的最后一个正序 a = max{ i | p(i) < p(i+1) } , 如果不存在说明当前排列即最后一个排列
2. 找到最后大于 p(i) 者 b = max{ j | p(i) < p(j) }
3. 互换 p(a) 与 p(b) 得 p(1),…,p(a-1),p(b),p(a+1),…,p(b-1),p(a),p(b+1),…,p(n)
4. 反排位置 a 后面的数得到结果

例如：求数列 {2,5,9,7,3} 的下一个排列。

1. 找到最后一个正序 {5,9}，则 a = 2 , p(a) = 5
2. 找到最后大于 p(2) = 5 的数，b = 4 , p(b) =7
3. 交换 p(2) = 5 和 p(4) = 7 的位置得 {2,7,9,5,3}
4. 反排位置 2 即 p(2) =7 后面 {9,5,3} 得结果 {2,7,3,5,9}

下面给出算法流程的 Java 及 Go 语言实现，讲解以 Java 为例

public static int[] nextPermutation(int[] array) {
  int lastPositive = findLastPositive(array);  // 找到最后一个正序的索引
  if (lastPositive == -1) {  // 找不到说明当前排列即为最后一个
    return null;
  }
  int[] next = new int[array.length];  // 到这里已经确定有最后一个了，先构造一个和原数组长度相同的数组
  System.arraycopy(array, 0, next, 0, lastPositive);  // 根据前面的分析，最后一个正序前面的元素是没有变的，先复制过来

  int lastLarge = findLastLarge(array, lastPositive);  // 找到 lastPositive 后面最后大于 array[lastPositive] 的数的索引
  /**
  *  交换位置，这里只对 lastPositive 位置赋值而不修改 lastLarge 位置
  *  是因为 lastLarge 在 lastPositive 之后且 lastPositive 后的数还需要倒排，
  *  先分析好交换及倒排后各数的位置可以减少一些中间操作
  *  i == array.length + lastPositive - lastLarge 即倒排后 lastLarge 位置的数，
  */
  next[lastPositive] = array[lastLarge]; 
  for (int i = lastPositive + 1; i < next.length; i++) {
    if (i == array.length + lastPositive - lastLarge) {
      next[i] = array[lastPositive];
    } else {
      next[i] = array[array.length + lastPositive - i];
    }
  }
  return next;
}

private static int findLastPositive(int[] array) {
  for (int i = array.length - 2; i >= 0; i--) {
    if (array[i] < array[i + 1]) {
      return i;
    }
  }
  return -1;
}

private static int findLastLarge(int[] array, int fromIndex) {
  for (int i = array.length - 1; i > fromIndex; i--) {
    if (array[i] > array[fromIndex]) {
      return i;
    }
  }
  return -1;
}

** 源码位置 **

• DictOrdinalUtil.java
• DictOrdinalTest.java
• dict_ordinal.go
• dict_ordinal_test.go