九、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)