学步园

九、Python编程解决组合问题（之二）

----From a high school student's view to learn Python

 

关键字：

python
组合问题 编程 递归 函数 元组 堆栈 列表 combination function recursive tuplelist stack

 

四、组合问题的通用算法

到这，肯定有人会问，有没有比这好懂一些的方法呢，这也是我当初的想法，其实在python的库中，就有非常好的实现，因为python本身就有直接解决排列、组合问题的函数提供:http://www.python.org/doc//current/library/itertools.html

在列表中你可以看到一个combinations的函数，函数的源代码如下：

def combinations(iterable, r):
    # combinations('ABCD', 2) --> AB AC AD BC BD CD
    # combinations(range(4), 3) --> 012 013 023 123
    pool = tuple(iterable)
    n = len(pool)
    if r > n:
        return
    indices = range(r)
    yield tuple(pool[i] for i in indices)
    while True:
        for i in reversed(range(r)):
            if indices[i] != i + n - r:
                break
        else:
            return
        indices[i] += 1
        for j in range(i+1, r):
            indices[j] = indices[j-1] + 1
        yield tuple(pool[i] for i in indices) 

如何使用？如下：

>>> importitertools

>>>a=('zhao','qian','sun','li','zhou','wu')

>>> for b initertools.combinations(a,4): print b

... 

('zhao', 'qian', 'sun', 'li')

('zhao', 'qian', 'sun', 'zhou')

('zhao', 'qian', 'sun', 'wu')

('zhao', 'qian', 'li', 'zhou')

('zhao', 'qian', 'li', 'wu')

('zhao', 'qian', 'zhou', 'wu')

('zhao', 'sun', 'li', 'zhou')

('zhao', 'sun', 'li', 'wu')

('zhao', 'sun', 'zhou', 'wu')

('zhao', 'li', 'zhou', 'wu')

('qian', 'sun', 'li', 'zhou')

('qian', 'sun', 'li', 'wu')

('qian', 'sun', 'zhou', 'wu')

('qian', 'li', 'zhou', 'wu')

('sun', 'li', 'zhou', 'wu')

 

看起来比我们实现的代码高明得多，能够解决任意序列的任意数量的组合问题；你可能会想，我们整这么多干啥？直接拿来用不就行了，其实，我们的真实目的是学习，学习就应该参考好的，提高自己；

 

我将这个程序进行了简单的改造:

 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

def combinations(iterable, n):     pool =tuple(iterable)    comb=[]     m =len(pool)     if n> m:        return comb     indices =range(n)     whileTrue:        while True:            comb.append(tuple(pool[i] for i in indices))            if indices[n-1] < m-1:                indices[n-1] += 1            else:                break        for i in reversed(range(n-1)):            if indices[i] != i + m - n:                indices[i] += 1                for j in range(i+1, n):                    indices[j] = indices[j-1] + 1                break        else:            return comb         print "\nChange from python itertools" comb1=combinations(('zhao','qian','sun','li','zhou','wu'),4) for e in comb1: print e print len(comb1)

 

 

可以直接copy形成一个.py文件直接运行，运行结果：

Change from python itertools

('zhao', 'qian', 'sun', 'li')

('zhao', 'qian', 'sun', 'zhou')

('zhao', 'qian', 'sun', 'wu')

('zhao', 'qian', 'li', 'zhou')

('zhao', 'qian', 'li', 'wu')

('zhao', 'qian', 'zhou', 'wu')

('zhao', 'sun', 'li', 'zhou')

('zhao', 'sun', 'li', 'wu')

('zhao', 'sun', 'zhou', 'wu')

('zhao', 'li', 'zhou', 'wu')

('qian', 'sun', 'li', 'zhou')

('qian', 'sun', 'li', 'wu')

('qian', 'sun', 'zhou', 'wu')

('qian', 'li', 'zhou', 'wu')

('sun', 'li', 'zhou', 'wu')

15

 

程序为什么会变的这么复杂呢？

1  程序考虑了广泛的适用性，能够针对任何的序列来解决组合的问题，而我们上面的程序只能够使用到自然数的数列中

2  程序考虑了意外的情况，如果序列中有6个元素，而你要找7个元素的组合，程序不会发生意外

3  程序没有使用递归，所以解决的过程需要考程序流程来处理

 

我们还是来讲讲这个程序本身，在开始之前，先介绍一下在这个程序中新出现的一个语法：

 

for语句后面的else

for 循环可以有
else用于循环后处理(post-processing)，while 循环中的else 处理方式相同，只要
for循环是正常结束的(不是通过 break),else子句就会执行

 

下面介绍程序的算法流程，把这个算法流程搞清楚，程序看起来就会简单很多，但是把这个算法用文字性的语言描述出来，我可真是费了九牛二虎之力：

1  为了使解决问题的方法具有普适性，我们在编写算法的过程中，不会直接的操作序列的每个元素，而是使用每个元素在序列中的序号来进行组合，序号从0开始，在最后形成结果时，再根据序号与序列中元素的对应关系，得到我们想要的结果，这样不管序列是多复杂的元素组成，我们都相当于在解决0~m-1这些数中n个数的组合

2  我们还是回到最开始的那10个步骤，我们之前讲过，对于每一步来说，就是最后的一个元素在进行循环，这具有普遍性，适用于C(m,n)，也就是说，对于从m个元素中取n个元素的组合，在确定了组合中的n-1个元素之后，剩下要做的就是进行循环，每一次的循环确定一个组合的第n个元素，形成一种组合结果。那么现在的难点在与如何程序化的确定那n-1个元素

3  我们再来分析一下那10个步骤，我们固定的3个数从1
23到最后变为3 4 5，看看每一步的变化，我们可以发现一些规律：

l 变化第三位开始，第①~第③，第三位从3->5

l 第三位变化完之后，改变第二位，同时，第三位起始位置也+1，重复上一步

l 上面两步重复执行，知道第二位变为4，再按照类似的步骤，对第一位进行变化，再重复以上两步

4   从上面的描述，最需要我们明白的一点是：除了最后一个数，其他的数只要一变化，这个数后面的数都要重新排序，再进行循环操作。

 

程序说明：

line1：函数定义，传入的参数1是序列，该序列可以是一个list或者tuple或者字符窜，参数2是组合中元素的数量

line2：将传入的参数强制转为tuple，如果是字符窜，如’ABCDEF’，在执行后，pool将等于('A','B', 'C',
'D', 'E', 'F')

line3：局部变量，初始化为空list，用来存储结果，并在最后作为返回值

line4：计算序列中元素的数量，保存在变量m中

line5-6：例外情况判断，如果要求组合的数量r<序列中元素的数量，直接返回空list

line7：中间变量，在前面的算法流程中讲过，组合的中间结果是用序号来表示的，这个list变量就是这个用途，而且初始化值是第一个组合的序号，如果是从m个元素中取4个的组合，那它的值就为[0,1,
2, 3]

line8：这个大的while循环，没执行一次循环，代表的就是我们最开始描述10步中的一步

line9-14：这是一个小循环，目的就是在固定了n-1个数之后，对最后一个数进行循环，并输出结果

line10：这一句从语法上讲最复杂，但从作用上看最简单，我们之前说过，组合的中间结果是元素的序号，为了得到真正的组合结果，还需要根据对应关系，进行一次转换，这就是本句的作用。看看句子本身，append的参数里包含了一个循环，很神奇，这也是python的神奇语法

line11-14：这是循环的是结束还是继续的判断语句，我们知道，最后一个数必须循环到为n-1为止（注意，这里所述的数为序号，序号是从0开始的），所以如果最后一个数比n-1小，就+1继续循环，否则，循环终止

line15-20：这是本程序最难懂的关键点，我们一句一句的说明

line15：for循环语句，我们在算法描述中说了，在最后一个序号循环结束之后，剩余的序号变化是从后往前的，所以我们使用reversed对range产生的list进行了倒转，而且由于这个循环的序号变化，只是针对前面的n-1个，所以range的范围是n-1

line16：判断语句，从最开始的例子，我们知道，对于6取4，固定的3个数从12 3变化为3
45之后，循环会终止，这条语句的目的就是从后往前，逐个的判断，条件是否满足，如果第三位变成了5，那就再循环，判断第二位，依次执行；

line17-20：对于line16的判断，假设第二位现在是3，就会执行17-20的语句，line17将第二位+1，line18-19的语句将第二位后面的重新排序，排序之后，line20的break语句跳出这个循环，继续line8的大循环

line21：如果line15-20的循环正常完成（正常完成指的是没有经过break语句跳出），说明12
3已经变为了3 4 5，那么程序就可以结束了

五、结束

用文字来描述这个过程，对我来说是非常有难度的挑战，但从个人的学习经历来看，网上可以找到很多的程序源代码，但是对于初学者，由于这些程序都没有一些详细的描述，所以看起来都比较的困难，所以我还是尝试把我理解的描述清楚，便于像我这样的初学者入门，否则很容易遇难而退。

 

我再说说我的一些体会，也希望可以对大家有搜帮助：

写程序的目的是解决实际的问题，但是程序也有基本的语法和一些基本的技巧，这些都需要从写一些小的应用程序着手，来积累自己的基础知识，想一下子成为高手，这也没有捷径。

解决某个实际的问题，程序的写法其实有很多种，就想我们在上面看到的组合问题，有很多种写法，其实针对只有一个问题，我们可以相处很多的问题来训练自己，比如：

我们能否将递归方法，也改为一个通用的程序，可以针对任意的序列来解决组合问题？

我们更改一下程序，让组合的产生顺序发生变化

其实，对一个问题的举一反三，就能够将python的基本语法掌握扎实了。