作者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/cn.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