0

我有一个由其他列表和一些零组成的列表，例如：

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 中应该相当容易，但我就是不明白。有人可以帮帮我吗？

4

3 回答 3

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]
于 2010-05-31T16:11:00.803 回答
2

我会做类似的事情......：

>>> 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]
>>>

当然，可以通过多种方式进行微优化，但我希望总体思路清晰：识别所有可能为零的索引集，并将原始列表的非零项按顺序放置在其他位置。

于 2010-05-31T16:25:22.647 回答
0

在 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))
于 2010-05-31T15:56:22.490 回答