2014-11-29
关于排列组合，可以在Permutation和Combination重温一下。这两个维基词条的中文版本把程序也给出来了。
全排列
假设有5个字符元素放在数组里：
['a', 'b', 'c', 'd', 'e']
取每个元素对应的下标：
[0, 1, 2, 3, 4]
对这个整型数组进行全排列，就可以得到那5个字符元素的全排列。
其实，由0, 1, 2, 3, 4这5个数组成所有可能的5位数就行了。那么如何生成这些5位数呢？
方法1：
假设5位数的每位都可以由0, 1, 2, 3, 4组成，那么这个5位数就是一个5进制数字。我们从小到大生成所有的5进制的5位数，对于每一个数，如果所有的位上没有包含0, 1, 2, 3, 4的所有，则舍弃；若都包含了，拿来用就行了。不建议该方法。
方法2： 假设当前的一个排列是：p=[0, 1, 2, 3, 4]，找到最大的下标j，使得p[j]<p[j+1]；然后，找到最大的下标k，使得p[k]>p[j]；调换p[k]和p[j]的值；将p[j+1], p[j+2], ..., p[4]反转。于是得到了下一个排列。
例如，当前排列为：p=[0, 1, 2, 3, 4]，可以找到j=3、k=4，调换p[k]和p[j]的值后得到a=[0, 1, 2, 4, 3]；j+1等于4，将p[4]反转，得到a=[0, 1, 2, 4, 3]。
当前排列为：p=[0, 1, 2, 4, 3]，可以找到j=2、k=4，调换p[k]和p[j]的值后得到p=[0, 1, 3, 4, 2]；j+1等于3，将p[3], p[4]反转，得到p=[0, 1, 3, 2, 4]。
这个算法能看出一些端倪，一个5位数由于0, 1, 2, 3, 4这5个数字组成，每个数字仅仅出现一次，最小值是01234；大于01234的最小值是01243；大于01243的最小值是01324。
这个算法的初始排列是：p=[0, 1, 2, 3, 4]。当在排列中找不到j，使得p[j]<p[j+1]时，算法结束。
全组合
假设有5个字符元素放在数组里：
['a', 'b', 'c', 'd', 'e']
要生成分别由1、2、3、4、5个元素形成的组合。
思路如下：
初始化一个同样大小的数组，p = [0, 0, 0, 0, 1]，由于p[4]等于1，所以将e拿出来作为一个组合。按照二进制的方式对p加1，得到p = [0, 0, 0, 1, 0]，于是将d拿出来作为一个组合。之后，p = [0, 0, 0, 1, 1]，于是将d, e拿出来作为一个组合，依次类推。
从n个元素中找到所有m个元素的组合
首先，m需要小于等于n。
仍然以下面5个元素为例：
['a', 'b', 'c', 'd', 'e']
则n=5。令m=2。
初始化一个大小为n的整型数组：p = [0, 0, 0, 1, 1]。由于d、e在数组p中对应的值为1，故得到组合d, e。之后，找到最大的j，使得p[j]<p[j+1]，调换p[j]和p[j+1]的值，然后将p中下标从j+2开始的元素（包括p[j+2]）中所有的1移动到p的最右边。利用这个思路找出所有的组合，直到在p中找不到j，使得p[j]<p[j+1]。
根据上面的思路，将依次得到下面的组合：
p = [0, 0, 0, 1, 1] # d, e
p = [0, 0, 1, 0, 1] # c, e
p = [0, 0, 1, 1, 0] # c, d
p = [0, 1, 0, 0, 1] # b, e
p = [0, 1, 0, 1, 0] # b, d
......
补充
关于排列组合，递归解法是比较常用的，但是存在效率问题，在理解上需要使用归纳的思路。m个数中取n个数的组合算法只给出了递归解法，算法之排列与组合算法给出了递归和非递归的思路。