十、Python編程解決組合問題（之二… · 高中生學編程--Python學習

## 九、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](http://www.python.org/doc//current/library/itertools.html) 在列表中你可以看到一個[combinations](http://www.python.org/doc//current/library/itertools.html)的函數，函數的源代碼如下： [![十、Python編程解決組合問題（之二）](https://box.kancloud.cn/2015-10-30_5632e1cc04fc3.gif "十、Python編程解決組合問題（之二）")](http://photo.blog.sina.com.cn/showpic.html#blogid=d6cca93e0101entc&url=http://album.sina.com.cn/pic/d6cca93egx6Dc1uUUWF95&690) ~~~ 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') 看起來比我們實現的代碼高明得多，能夠解決任意序列的任意數量的組合問題；你可能會想，我們整這么多干啥？直接拿來用不就行了，其實，我們的真實目的是學習，學習就應該參考好的，提高自己；我將這個程序進行了簡單的改造: <table border="1" cellspacing="0" cellpadding="0" style="border-collapse:collapse; border:none"><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">123456789101112131415161718192021222324252627?</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 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 eprint len(comb1)?</td></tr></tbody></table> 可以直接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，看看每一步的變化，我們可以發現一些規律：變化第三位開始，第①~第③，第三位從3->5 第三位變化完之后，改變第二位，同時，第三位起始位置也+1，重復上一步上面兩步重復執行，知道第二位變為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的基本語法掌握扎實了。我的更多文章： - Python程序調試的一些體會(2013-10-06 22:57:35) - 十四、Python編程計算24點（之二）(2013-10-03 22:18:28) - 十三、Python編程計算24點（之一）![](https://box.kancloud.cn/2015-10-30_5632e1cc04fc3.gif "此博文包含圖片") (2013-10-02 22:15:46) - 十二、Python簡單數據結構應用（之二）(2013-10-02 22:10:41) - 十一、Python簡單數據結構應用（之一）(2013-09-23 23:31:49) - 九、Python編程解決組合問題（之一）(2013-09-21 23:32:54) - 八、Python的函數編程（之二）![](https://box.kancloud.cn/2015-10-30_5632e1cc04fc3.gif "此博文包含視頻") (2013-09-20 23:09:39) - 七、Python的函數編程（之一）![](https://box.kancloud.cn/2015-10-30_5632e1cc04fc3.gif "此博文包含視頻") (2013-09-20 23:09:10) - 六、Python的程序流程(2013-09-19 16:53:58) - 高中生如何學編程(2013-09-02 19:26:01)