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

发布于 2024-09-03 10:42:56 字数 351 浏览 9 评论 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 中应该相当容易，但我就是不这么认为。有人可以帮我吗？

原文

I have a list consisting of other lists and some zeroes, for example:

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

I would like to generate all the combinations of this list while keeping the order of the inner lists unchanged, so

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

is fine, but

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

isn't. I've got the feeling that this should be fairly easy in Python, but I just don't see it. Could somebody help me out?

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

梦巷 2024-09-10 10:42:56

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

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

当然，可以在很多方面进行微观优化，但我希望总体思路是明确的：识别所有可能有零的索引集，并将非零项放入其他地方的原列表按顺序排列。

I'd do something like...:

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

Can be micro-optimized in many ways, of course, but I hope the general idea is clear: identify all the set of indices that could have zeros, and put the non-zero items of the original list in the other places in order.

回复收藏 0 原文

月寒剑心 2024-09-10 10:42:56

一个提示：如果有 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]

One hint: If there are z zeros and t lists then the number of combinations you describe is choose(z+t, z). (The stars and bars trick will help to see why that's true.)

To generate those combinations, you could generate all the length-z subsets of {1,...,z+t}.
Each of those would give the positions of the zeros.

Even better, here's a generalization of your question:

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

Your input x can be converted into a form y suitable for the above generalization as follows:

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]

回复收藏 0 原文

乖乖兔^ω^ 2024-09-10 10:42:56

在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))

In 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))

回复收藏 0 原文

~没有更多了~