作者SocketAM2 (AM2)
看板Python
標題Re: [問題] 排列組合問題
時間Sat May 21 00:16:48 2016
※ 引述《bibo9901 (function(){})()》之銘言：
: 標題: 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)
這邊我有些不同的看法...
"有辦法做出所有1開頭的合法序列, 透過輪換就可以得到所有的序列"
這句話原則上是沒錯
但實用上沒有若沒有進一步的巧思可能還是沒法好用
注意到上面用(1,2,1,4)輪換出的(1,4,1,2)
他同樣是在1開頭的合法序列中
稍後要對(1,4,1,2)再做輪換時要跳過才能避免重複
又例如對(1,1,1,1)做輪換顯然是對應另外2,3,4的三組序列而不是7組
b大在上面提供的八個一組輪換並不適用所有元素，還需要再加工
以原po所說"想產生一個包含所有滿足某條件的list"這樣的需求
我揣測至少有兩類常見的後續動作的可能性:
1. 想知道在各個N下滿足條件的元素的個數
2. 想iterate過整個list做後續處理 (單純印出來存下來也屬於此類)
若不能保證產生的list沒有重複，對以上這兩類應用不好直接用
如果原po的需求只是上述的1.
那利用b大提供的、或其他各種遞迴關係嘗試解通式是很棒的
如果需求是第二種，要達到時間複雜度大O最佳似乎並不困難
差別只在實作細節影響的係數上
考慮到存整個list對空間複雜度的需求
我覺得前陣子用過的generator作法值得提出來給你參考
僅占用少數記憶體空間就可以iterate所有解是最主要的好處
請參考Gist處女秀! 有請各位大大不吝指正
https://gist.github.com/socketam2/a46413f9ecea0e4a805801c585608ef3
如果正確性沒問題的話，
這邊第二種優化的版本比第一種快一倍多
N=13時，清點近160萬個組合，耗時4.110 sec VS 1.712 sec
*************************
強力推薦 <Python2.7>/Lib/test/test_generator.py
我覺得這邊的各種test都很有啟發性啊
*************************
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 58.114.176.157
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Python/M.1463761011.A.B49.html
1F：→ bibo9901: 對 我沒想清楚 那重覆的可以不用做@@ 05/21 00:38
2F：推 feynmankao: 感謝你~我的需求的確是2，我需要用這個list做其它事~ 05/21 21:23
如果只需要"一次一個"的掃過整個list的話
很適合用generator邊產生元素邊做 不用等整個list生成喔
另請問你的N需要多大呢?
※ 編輯: SocketAM2 (58.114.176.157), 05/21/2016 22:54:46
3F：推 feynmankao: 其實我的N不會太大，20以下就有很好的效果了 05/21 23:25
囧，N=20的話大概有5*10^9個元素
我猜你應該一定需要generator了
就算是用2個bit表示每個1234，
整個列表也需要約2*20*5*10^9 bit = 25 GByte
如果真是用python的list的話應該需要這數字的20倍以上 (甚至接近100倍)
而且這還只是"存著這些列表"，什麼後續動作都還沒做
我的code雖然記憶體用的少(<3MB吧)，但速度可能還不夠用
如果你願意分享(或其他版友有有興趣的話)
我很想見識一下這問題能加速到多快
※ 編輯: SocketAM2 (58.114.176.157), 05/21/2016 23:42:51
補個結果 (i5-2400, DDR3-1333)
N = 20 : count = 3486784404, iter_time = 4004 sec
※ 編輯: SocketAM2 (58.114.176.157), 05/22/2016 00:11:04