九、Python编程解决组合问题（之一…
最后更新于：2022-04-01 21:47:35
## 九、Python编程解决组合问题（之一）
----From a high school student's view to learn Python
关键字：
python组合问题 编程 递归 函数 元组 堆栈 列表 combination function recursive tuplelist stack
一、组合问题概述
组合是指从给定个数的元素中仅仅取出指定个数的元素，不考虑排序。组合的公式如下：
从m个元素中取n个元素的组合记为：C(m,n)，则：
C(m, n) = m!/((m-n)!n!)
在知道了组合的定义以及公式之后，我们要求比如9个数中取4个数的组合以及列出各种组合，是非常简单的，C(9,4)=126。
我开始也想当然，用计算机来解决组合问题，那是不是太小儿科了，可当我一开始着手做，才知道这还真不是一个简单的问题。当然对于计算组合的数量是非常简单（其实，对于我们刚开始学习编程，写一个计算组合数量的程序也不算很简单），那复杂在什么地方呢？
对于C(9,4)，复杂在于我们如何将所有的组合列出，我们先拿6个数来举例。
列出1 2 3 4 5 6六个数的所有任意四个数的组合
1 固定1 2 3，组合有：1234 1235 1236
2 固定1 2 4，组合有：1245 1246
3 固定1 2 5，组合有：1256
4 固定1 3 4，组合有：1345 1346
5 固定1 3 5，组合有：1356
6 固定1 4 5，组合有：1456
7 固定2 3 4，组合有：2345 2346
8 固定2 3 5，组合有：2356
9 固定2 4 5，组合有：2456
10 固定3 4 5，组合有：3456
共计15种，与C(6,4)=6*5*4*3/(1*2*3*4)=15相符。
二、组合问题的简单算法
如何把这些步骤进行归纳总结，形成一个算法，通过编程让计算机可以自动完成列出各种组合的任务呢？这下你应该体会到，计算机其实并不“聪明”，如果没有人给它执行指令，它其实啥也不会做。言归正传，我们还是来分析一下，这个问题如何解决：
首先，我们分析上面列出的10个步骤，对于1），很明显，在固定了1 23这三个数之后，第四个数就是4、5、6三个数进行了循环（还记得循环吗，计算机最拿手的就是做循环）。
其次，我们再分析1）2）3）这三个步骤中固定的数字，前两个没有变，都是12，只是第三个数在进行循环（又是循环）。
通过分析，我们可以找到这样的规律：
1 先固定3个数，让第四个数进行循环
2 让第三个数循环，重复第一步
3 让第二个数循环，重复第一步
4 让第一个数循环，重复第一步
似乎几个循环就能够搞定，确实如此，看看下面的程序：
程序的运行结果如下：
[1, 2, 3, 4]
[1, 2, 3, 5]
[1, 2, 3, 6]
[1, 2, 4, 5]
[1, 2, 4, 6]
[1, 2, 5, 6]
[1, 3, 4, 5]
[1, 3, 4, 6]
[1, 3, 5, 6]
[1, 4, 5, 6]
[2, 3, 4, 5]
[2, 3, 4, 6]
[2, 3, 5, 6]
[2, 4, 5, 6]
[3, 4, 5, 6]
Using Loop: 15
对这个程序，做一些说明：
程序使用了函数，函数名为combNumberLoop4
l程序使用了循环，而且是一个多重循环，注意：循环的缩进，循环的变量，循环的范围；每一层的循环，range的起始值都依赖于上一层的循环变量，如果对range函数还有疑问的，请复习一下。
l程序设置了一个计数的变量totalNumber，每算出一种组合，变量+1；
l程序有一个return语句，用来返回总共有多少种组合；
l程序中使用了列表(list)数据类型，我们先初始化了一个有四个元素的list变量group，group在程序中作为参数，传入到函数中使用，在函数的定义中，我们使用b来接收group，所以在函数中，对于b的操作其实就是对group的操作。函数中有对list中单个元素进行更新；
l对于print语句的使用，我们使用了格式化输出，用来显示计算列出的组合数量；
l对于函数的调用，我们直接把调用放在了print语句中，显示了python的灵活语法规则；
l再一次的强调“缩进”“:”，特别是“缩进”，经常会引起莫名其妙的问题，教训深刻；
我们把变量group在调用函数时，作为参数在传入，那再函数调用返回之后，group的值改变了吗？请大家自己试一试。
组合问题似乎就这么顺利的解决了，但恐怕没有这么简单：
你有没有发现，这个函数有一个严重的缺陷（思考一下），它只能够解决四个数的组合问题。
如果你想解决非四个数的组合问题，那你还得再写一个函数，可是在程序中，为了解决通用型的问题，类似C(m,n)，m、n都会是变化的，我们总不能写n个函数来实现吧？我们似乎应该找一个更通用的办法。
三、组合问题的递归解决
我们再回到C(6,4)问题，除了上面列出的十个步骤，我们换个思路：
如果在6个数中选定一个数，那么确定剩下的3个数是不是变为了“从5个数中选3个数的组合问题”了呢？以此类推，这似乎变成了一个“递归”问题了，确实，我们可以用递归的思路来解决这个问题。
对于C(m,n)列出所有组合的问题，可以按照一下的步骤来进行编程，这次我们按从后往前的顺序来列出所有组合：
1 选定一个元素i，在范围[m, n]内进行循环
2 将i 作为所求组合的最后一个元素
3 如果n-1>0，进行递归调用，求C(m-1,n-1)；否则，输出结果
4 重复①
注意，设计递归函数一定要有终止条件，否则会造成“死循环”。
实现的代码如下：
运行结果：
[3, 4, 5, 6, 7]
[2, 4, 5, 6, 7]
[1, 4, 5, 6, 7]
[2, 3, 5, 6, 7]
[1, 3, 5, 6, 7]
[1, 2, 5, 6, 7]
[2, 3, 4, 6, 7]
[1, 3, 4, 6, 7]
[1, 2, 4, 6, 7]
[1, 2, 3, 6, 7]
[2, 3, 4, 5, 7]
[1, 3, 4, 5, 7]
[1, 2, 4, 5, 7]
[1, 2, 3, 5, 7]
[1, 2, 3, 4, 7]
[2, 3, 4, 5, 6]
[1, 3, 4, 5, 6]
[1, 2, 4, 5, 6]
[1, 2, 3, 5, 6]
[1, 2, 3, 4, 6]
[1, 2, 3, 4, 5]
Using Recursive: 21
我们还是按照之前的方式对程序进行一些解释：
这是一个通用的程序，这个程序没有前一个程序的限制，可以解决从1~m的数中取n个数的组合问题
为了返回正确的组合数量的统计值，我们设置了变量totalNumberR，注意该变量我们在函数中将它使用global强制转为全局变量，大家可以试一试，如果不这样做，看看返回的结果是什么
从执行结果来看，这次的组合与之前的例子不同，是从最后面的一组组合开始的，在函数的循环中，range使用的步进值为-1
因为要求5个元素的组合，我们将group初始化为5个元素的list
注意递归调用的参数
递归的使用，让程序写起来非常的简洁，但是，在写程序的时候，我有两个地方（其实程序也就难在这两个地方），折腾了好几天才弄清楚：
首先是for循环的循环范围如何确定；
其次是递归调用时使用的参数设计；
和之前介绍递归函数时使用的斐波那契数列的例子，这个程序更难理解执行的顺序，不象fib，只是层层调用而已，而这个程序在调用外面还套了一层循环，增加了理解的难度。
我的更多文章：
- [Python程序调试的一些体会](http://blog.sina.com.cn/s/blog_d6cca93e0101ewc9.html)(2013-10-06 22:57:35)
- [十四、Python编程计算24点（之二）](http://blog.sina.com.cn/s/blog_d6cca93e0101euxx.html)(2013-10-03 22:18:28)
- [十三、Python编程计算24点（之一）](http://blog.sina.com.cn/s/blog_d6cca93e0101eukc.html)
(2013-10-02 22:15:46)
- [十二、Python简单数据结构应用（之二）](http://blog.sina.com.cn/s/blog_d6cca93e0101euk8.html)(2013-10-02 22:10:41)
- [十一、Python简单数据结构应用（之一）](http://blog.sina.com.cn/s/blog_d6cca93e0101ep9z.html)(2013-09-23 23:31:49)
- [十、Python编程解决组合问题（之二）](http://blog.sina.com.cn/s/blog_d6cca93e0101entc.html)
(2013-09-21 23:37:27)
- [八、Python的函数编程（之二）](http://blog.sina.com.cn/s/blog_d6cca93e0101ekwj.html)
(2013-09-20 23:09:39)
- [七、Python的函数编程（之一）](http://blog.sina.com.cn/s/blog_d6cca93e0101ekwg.html)
(2013-09-20 23:09:10)
- [六、Python的程序流程](http://blog.sina.com.cn/s/blog_d6cca93e0101ejeg.html)(2013-09-19 16:53:58)
- [高中生如何学编程](http://blog.sina.com.cn/s/blog_d6cca93e0101e8fn.html)(2013-09-02 19:26:01)
';
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | def combNumberLoop4(m, b): group=[99,99,99,99] print "\nUsing Loop: %d\n" % combNumberLoop4(6, group) |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | def combNumber(m, n, b): group=[99,99,99,99,99] totalNumberR = 0 print "\nUsing Recursive: %d\n" % combNumber(7,5,group) |