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