生成所有有排序约束的排列

Question

我有一个列表，这个列表里面包含了其他列表和一些零，比如：

x = [[1, 1, 2], [1, 1, 1, 2], [1, 1, 2], 0, 0, 0]

我想生成这个列表的所有组合，同时保持里面的列表顺序不变，所以

[[1, 1, 2], 0, 0, [1, 1, 1, 2], [1, 1, 2], 0]

是可以的，但

[[1, 1, 1, 2], [1, 1, 2], 0, 0, [1, 1, 2], 0]

就不行。我觉得在Python中这应该很简单，但我就是想不明白。有人能帮我一下吗？

Answer 1

我会这样做...:

>>> import itertools
>>> x = [[1, 1, 2], [1, 1, 1, 2], [1, 1, 2], 0, 0, 0]
>>> numzeros = x.count(0)
>>> listlen = len(x)
>>> where0s = itertools.combinations(range(listlen), numzeros)
>>> nonzeros = [y for y in x if y != 0]
>>> for w in where0s:
...   result = [0] * listlen
...   picker = iter(nonzeros)
...   for i in range(listlen):
...     if i not in w:
...       result[i] = next(picker)
...   print result
... 
[0, 0, 0, [1, 1, 2], [1, 1, 1, 2], [1, 1, 2]]
[0, 0, [1, 1, 2], 0, [1, 1, 1, 2], [1, 1, 2]]
[0, 0, [1, 1, 2], [1, 1, 1, 2], 0, [1, 1, 2]]
[0, 0, [1, 1, 2], [1, 1, 1, 2], [1, 1, 2], 0]
[0, [1, 1, 2], 0, 0, [1, 1, 1, 2], [1, 1, 2]]
[0, [1, 1, 2], 0, [1, 1, 1, 2], 0, [1, 1, 2]]
[0, [1, 1, 2], 0, [1, 1, 1, 2], [1, 1, 2], 0]
[0, [1, 1, 2], [1, 1, 1, 2], 0, 0, [1, 1, 2]]
[0, [1, 1, 2], [1, 1, 1, 2], 0, [1, 1, 2], 0]
[0, [1, 1, 2], [1, 1, 1, 2], [1, 1, 2], 0, 0]
[[1, 1, 2], 0, 0, 0, [1, 1, 1, 2], [1, 1, 2]]
[[1, 1, 2], 0, 0, [1, 1, 1, 2], 0, [1, 1, 2]]
[[1, 1, 2], 0, 0, [1, 1, 1, 2], [1, 1, 2], 0]
[[1, 1, 2], 0, [1, 1, 1, 2], 0, 0, [1, 1, 2]]
[[1, 1, 2], 0, [1, 1, 1, 2], 0, [1, 1, 2], 0]
[[1, 1, 2], 0, [1, 1, 1, 2], [1, 1, 2], 0, 0]
[[1, 1, 2], [1, 1, 1, 2], 0, 0, 0, [1, 1, 2]]
[[1, 1, 2], [1, 1, 1, 2], 0, 0, [1, 1, 2], 0]
[[1, 1, 2], [1, 1, 1, 2], 0, [1, 1, 2], 0, 0]
[[1, 1, 2], [1, 1, 1, 2], [1, 1, 2], 0, 0, 0]
>>> 

当然，这个方法可以通过很多方式进行小优化，但我希望大家能明白大致的思路：找出所有可能为零的索引，然后把原始列表中非零的项目按顺序放到其他位置。

Answer 2

有一个提示：如果有 z 个零和 t 个列表，那么你描述的组合数量是 选择(z+t, z)。这个结果可以通过 星星与条形 的方法来理解，看看为什么是这样的。

为了生成这些组合，你可以生成 {1,...,z+t} 的所有长度为 z 的子集。每一个子集都会告诉你零的位置。

更进一步，这里有一个你问题的推广版本：

https://stackoverflow.com/questions/2944987/all-the-ways-to-intersperse

你的输入 x 可以转换成适合上述推广的形式 y，方法如下：

x = [[1,1,2], [1,1,1,2], [1,1,2], 0, 0, 0]
lists = [i for i in x if i != 0]
zeros = [i for i in x if i == 0]
y = [lists, zeros]

Answer 3

在Python 2.6中，

import itertools

def intersperse(x, numzeroes):
    for indices in itertools.combinations(range(len(x) + numzeroes), numzeroes):
        y = x[:]
        for i in indices:
            y.insert(0, i)
        yield y

x = [[1, 1, 2], [1, 1, 1, 2], [1, 1, 2]]
list(intersperse(x, 3))