作者bibo9901 (function(){})()
看板Python
標題Re: [問題] 排列組合問題
時間Thu May 19 03:04:12 2016
※ 引述《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://webptt.com/m.aspx?n=bbs/Python/M.1463598255.A.47F.html
1F：推 feynmankao: 感恩大大~ 05/19 03:27
※ 編輯: bibo9901 (140.112.16.139), 05/19/2016 11:58:18