排列组合的非递归算法

2014-11-29

关于排列组合,可以在PermutationCombination重温一下。这两个维基词条的中文版本把程序也给出来了。

全排列


假设有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=3k=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=2k=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]。由于de在数组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个数的组合算法

算法之排列与组合算法

关于排列组合,递归解法是比较常用的,但是存在效率问题,在理解上需要使用归纳的思路。m个数中取n个数的组合算法只给出了递归解法,算法之排列与组合算法给出了递归和非递归的思路。

( 完 )