九、Python编程解决组合问题（之一… · 高中生学编程--Python学习

## 九、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 让第一个数循环，重复第一步似乎几个循环就能够搞定，确实如此，看看下面的程序： <table border="1" cellspacing="0" cellpadding="0" style="border-collapse:collapse;mso-table-layout-alt:fixed;border:none; mso-padding-alt:0cm 5.4pt 0cm 5.4pt"><tbody><tr><td width="35" valign="top" style="width:35.0pt;border:solid black 1.0pt; border-right:solid #368174 3.0pt;background:white;padding:0cm 5.4pt 0cm 5.4pt">12345678910111213141516</td><td width="504" valign="top" style="width:504.0pt;border:solid black 1.0pt; border-left:none;background:white;padding:0cm 5.4pt 0cm 5.4pt">def combNumberLoop4(m, b): totalNumber= 0 for i inrange(1, m+2-4): b[0] = i for j in range(i+1, m+2-3): b[1] = j for k in range(j+1, m+2-2): b[2] = k for l in range(k+1, m+2-1): b[3] = l print b totalNumber += 1 returntotalNumber group=[99,99,99,99]print "\nUsing Loop: %d\n" % combNumberLoop4(6, group) </td></tr></tbody></table> 程序的运行结果如下： [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 重复① 注意，设计递归函数一定要有终止条件，否则会造成“死循环”。实现的代码如下： <table border="1" cellspacing="0" cellpadding="0" style="border-collapse:collapse;mso-table-layout-alt:fixed;border:none; mso-padding-alt:0cm 5.4pt 0cm 5.4pt"><tbody><tr><td width="35" valign="top" style="width:35.0pt;border:solid black 1.0pt; border-right:solid #368174 3.0pt;background:white;padding:0cm 5.4pt 0cm 5.4pt">1234567891011121314</td><td width="504" valign="top" style="width:504.0pt;border:solid black 1.0pt; border-left:none;background:white;padding:0cm 5.4pt 0cm 5.4pt">def combNumber(m, n, b): globaltotalNumberR for i inrange(m, n-1,-1): b[n-1] = i if n-1>0: combNumber(i-1,n-1,b) else: print b totalNumberR += 1 returntotalNumberR group=[99,99,99,99,99]totalNumberR = 0print "\nUsing Recursive: %d\n" % combNumber(7,5,group) </td></tr></tbody></table> 运行结果： [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)![](https://box.kancloud.cn/2015-10-30_5632e1cc04fc3.gif "此博文包含图片") (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)![](https://box.kancloud.cn/2015-10-30_5632e1cc04fc3.gif "此博文包含图片") (2013-09-21 23:37:27) - [八、Python的函数编程（之二）](http://blog.sina.com.cn/s/blog_d6cca93e0101ekwj.html)![](https://box.kancloud.cn/2015-10-30_5632e1cc04fc3.gif "此博文包含视频") (2013-09-20 23:09:39) - [七、Python的函数编程（之一）](http://blog.sina.com.cn/s/blog_d6cca93e0101ekwg.html)![](https://box.kancloud.cn/2015-10-30_5632e1cc04fc3.gif "此博文包含视频") (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)