[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分别是第二个数组的起始位置和结束位置,当两者相等时,右边的数组只有一个元素,这时就可以直接输出排列的数组。
一般情况下,交换当前元素和右边数字中的一个,递归排列,在结束时交换回来(这步是必须的)。

另一个是组合。组合相比排列要难一些,可能因为我没想清楚的原因。同样,组合[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,依次类推。