箱猫日和

[Java]排列和组合算法

下午花了点时间，把排列和组合算法搞出来了。网上一堆资料看了不靠谱，要么是不明所以的变量名，要么直接帖代码。

排列

实现要点：交换和顺序处理。考虑对[1, 2, 3, 4]排列。实际是排列

[1], [2, 3, 4]
[2], [1, 3, 4]
[3], [2, 1, 4]
[4], [2, 3, 1]

排列[1], [2, 3, 4]时，实际是排列

[1, 2], [3, 4]
[1, 3], [2, 4]
[1, 4], [3, 2]

从上面的分解可以看出，代码中实际要做的是交换当前的数字和右边数字中的某一个，具体来说，第一步是分别交换第一个和第一个，第一个和第二个，第一个和第三个，第一个和第四个。第二步是交换第二个和第二个，第二个和第三个，第二个和第四个。依次类推。递归的停止条件是右边的数组仅有一个元素，比如[1, 2, 3], [4]。具体代码如下，注意参数比较多的permutation方法。
start和end分别是第二个数组的起始位置和结束位置，当两者相等时，右边的数组只有一个元素，这时就可以直接输出排列的数组。
一般情况下，交换当前元素和右边数字中的一个，递归排列，在结束时交换回来（这步是必须的）。

import java.util.Arrays;

public class Permutation {

  private <T> void swap(T[] array, int i, int j) {
    if (i == j) return;
    T x = array[i];
    array[i] = array[j];
    array[j] = x;
  }

  private <T> void permutation(T[] array, int start, int end) {
    if (start == end) {
      System.out.println(Arrays.toString(array));
    } else {
      for (int i = start; i <= end; i++) {
        swap(array, i, start);
        permutation(array, start + 1, end);
        swap(array, start, i);
      }
    }
  }

  public <T> void permutation(T[] array) {
    permutation(array, 0, array.length - 1);
  }

  public static void main(String[] args) {
    Permutation p = new Permutation();
    p.permutation(new Integer[] {1, 2, 3, 4});
  }

}

另一个是组合。组合相比排列要难一些，可能因为我没想清楚的原因。同样，组合[1, 2, 3, 4]中两个数字。第一步

1 + 组合[2, 3, 4]中的一个
2 + 组合[3, 4]中的一个
3 + 组合[4]中的一个（实际就是4）

第二步，因为是两个数字，所以实际是终止条件。考虑 组合[1]中的一个 + 组合[2, 3, 4]中的一个。

1 + 2
1 + 3
1 + 4

可以看到在组合剩下只有一个的时候就可以输出了，即终止条件是组合1个数字的时候。
其次，在第一步分配的时候，因为组合不考虑顺序，所以并没有交换顺序。
第三，可以看到输出的时候因为没有交换顺序，所以输出的数字位置是不定的。如果为了输出交换位置可能会比较复杂，这里使用一个辅助数组表示当前组合的数字的索引。
具体代码如下，注意参数比较多的combination方法。
n == 1表示终止条件，首先根据indexes这个辅助数组获取前 n – 1组合的数组。在剩下的数字中任意选择一个输出。
否则，从开始位置，设置某个数字为组合中的一个数字，并递归尝试剩下的数组。注意，这里for的结束条件是length – n。比如三个数字中选两个，顺序组合的话，第一个数字只能选择位置1和位置2的，位置3的只能组成一个数字的组合。
其次有点要注意的是indexes是从0开始计数的，但是n是从大往小减的，所以实际索引计算为indexes长度减去n，比如一开始的时候是0，之后差为1，依次类推。

public class Combination {

  public <T> void combination(T[] array, int n) {
    combination(array, new int[n], 0, n);
  }

  public <T> void combination(T[] array, int[] indexes, int start, int n) {
    if (n == 1) {
      String prefix = generatePrefix(array, indexes);
      for (int i = start; i < array.length; i++) {
        System.out.print(prefix);
        System.out.print(array[i]);
        System.out.println(']');
      }
    } else {
      for (int i = start; i <= array.length - n; i++) {
        indexes[indexes.length - n] = i;
        combination(array, indexes, i + 1, n - 1);
      }
    }
  }

  private <T> String generatePrefix(T[] array, int[] indexes) {
    StringBuilder prefixBuilder = new StringBuilder("[");
    for (int i = 0; i < indexes.length - 1; i++) {
      prefixBuilder.append(array[indexes[i]]).append(", ");
    }
    return prefixBuilder.toString();
  }

  public static void main(String[] args) {
    Combination c = new Combination();
    c.combination(new Integer[] {1, 2, 3, 4, 5, 6}, 3);
  }

}

xnnyygn