Re: [問題] 排列組合問題

看板Python作者bibo9901 (function(){})()時間9年前 (2016/05/19 03:04)推噓1(1推 0噓 0→)

留言1則, 1人參與討論串2/3 (看更多)

※ 引述《feynmankao (最愛我的老婆!)》之銘言： : 大家好，我是python初學者，碰到一個各位高手應該都可以秒殺的問題 : 我現在想要弄出一個list含有一個變數n: 先稱為L(n) : L(n) 是一堆list 組成的 list。 : L(1) = [[1],[2],[3],[4]] : L(2) = [[1,1],[1,2],[1,4],[2,1],[2,2],[2,3],[3,2],[3,3], : [3,4],[4,1],[4,3],[4,4]] : ... : 簡單的說 L(n) 是所有長度為 n 且滿足下列條件(1)(2)(3) list L(n)[i] 的 list : 條件(1): 在 L(n)[i] 裡的元素都取自 [1,2,3,4] : 條件(2): 元素1和3 不能相鄰; 2和4不能相鄰 : 條件(3): L(n)[i] 頭尾二個元素要滿足，如果頭是1，尾就不能是3; : 頭是3，尾就不能是1; 頭是2，尾就不能是4; 頭是4 尾就不能是2 : ------ : 比如說 [1,1,1], [1,1,2],[1,1,4],[1,2,1],[1,2,2]... 都會在L(3) 裡 : 但 [1,3,2], [1,2,4] 不滿足(2); [1,2,3], [4,1,2] 不滿足(3) 都不會在L(3)裡 : ------ : 我保證這不是學校作業，這是我研究上要用到的計算，不過因為初學Sage， : 所以python語言還不是很熟練，希望大家指點一下。 : 感恩~ 你只要有辦法做出"所有1開頭的合法序列", 透過輪換就可以得到所有的序列例如, 假設我們已經知道 (1,2,1,4) 是合法的, 那我們很快就可以產出另外 7 種 1 2 3 4 (1,2,1,4) * 已知 1 4 3 2 (1,4,1,2) 1用1取代, 2用4取代, 3用3取代, 4用4取代 2 1 4 3 (2,1,2,3) 1用2取代, 2用1取代, 3用4取代, 4用3取代 2 3 4 1 (2,3,2,4) 以下類推 3 2 1 4 (3,2,3,4) 3 4 1 2 (3,4,3,2) 4 1 2 3 (4,1,4,3) 4 3 2 1 (4,3,4,1) 所以我們只要關心L(n)中 "1開頭" 的就好, 就把這些稱作 E(n) 吧考慮 E(n) 的倒數1,2位, 顯然只有下面幾種可能 1 ... 1 1 1 ... 1 2 1 ... 1 4 (A) 1 ... 2 1 1 ... 2 2 (B) 1 ... 3 2 1 ... 3 4 (C) 1 ... 4 1 1 ... 4 4 (D) 其中 (A),(B),(D) 的 1 ~ n-1 位恰好就是 E(n-1) (C) 稍麻煩一點, 它們的 1 ~ n-2 位是 "E(n-2)中以{2,4}結尾的序列" 總結起來就是 for s in E[n-1]: E[n].append( s + s[-1] ) if s[-1] == 1: E[n].append( s + [2] ) E[n].append( s + [4] ) else: E[n].append( s + [1] ) for s in E[n-2]: if s[-1] != 1: E[n].append( s + [3,2] ) E[n].append( s + [3,4] ) 現在只剩下兩件事就是手動列出 E[1]、E[2] 和從 E[n] 產生 L[n] 就交給你了 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.24.120.49 ※ 文章網址: https://www.ptt.cc/bbs/Python/M.1463598255.A.47F.html