作者feynmankao (最愛我的老婆!)
看板Python
標題[問題] 排列組合問題
時間Thu May 19 00:50:04 2016
大家好，我是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語言還不是很熟練，希望大家指點一下。
感恩~
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 66.254.234.150
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Python/M.1463590207.A.392.html
1F：推 IKAFIRE: itertools.product()再用你的規則下去篩選？ 05/19 01:08
2F：→ chienweichih: 直覺的做法是三個條件寫三個if, 然後暴力解 05/19 01:12
3F：→ bibo9901: 其實就是{1,3}和{2,4}兩類交錯排列而已 05/19 01:39
4F：→ bibo9901: 只要先產出字典序最小的 剩下的用旋轉就好了 05/19 01:42
5F：→ bibo9901: 嗯...想想不用這麼麻煩 05/19 01:52
6F：推 IKAFIRE: 他同數字可以相鄰，所以不是13和24交錯排 05/19 02:02
7F：推 SocketAM2: ATCG 05/19 02:13
8F：→ feynmankao: 請問各位高手，能多給一些線索或是資料嗎？我是真的 05/19 02:29
9F：→ feynmankao: 菜不是假的菜，如果可以多給一點線索的話，我應該可 05/19 02:30
10F：→ feynmankao: 以模仿寫出來~ 謝謝大家~ 05/19 02:31
11F：推 s06yji3: Back tracking 05/19 02:32
12F：→ bigpigbigpig: 用 zip 和 set 就可以搞定了 :) 05/19 02:37
14F：推 s06yji3: 我好像忘了加重複判斷 05/19 02:50
15F：→ mikapauli: 把將條件3變成固定頭尾所得到集合記為L(n,h,t) 05/19 02:51
16F：→ mikapauli: 則L(n)為其中12個L(n,h,t)的連集 05/19 02:52
17F：→ mikapauli: L(n,h,t)為9個L(n-2,h,t)的連集，遞迴可得。 05/19 02:53
18F：→ mikapauli: 看起來像被條件3篩選的雙生成自由群 05/19 02:57
19F：→ feynmankao: m大真眼尖，這的確跟F2(2個生成元的自由群)有關 05/19 03:24
20F：→ feynmankao: 謝謝大家，我會研究看看的~ 05/19 03:24
22F：→ feynmankao: 感謝大豬大~ 05/19 08:38
23F：→ mikapauli: minimal normal subgroup? 05/19 16:05
24F：→ mikapauli: 好像也不是 05/20 00:16
25F：→ feynmankao: 我是要cyclically reduced words的列表 05/24 09:44