生成具有某种约束的所有排列

我有由其他列表和一些零的列表，例如：生成具有某种约束的所有排列

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中这应该相当容易，但我只是没有看到它。有人能帮我吗？

来源

2010-05-31 Moos Hueting

此问题的更一般版本：http://stackoverflow.com/questions/2944987/all-the-ways-to-intersperse – dreeves 2010-05-31 18:14:04

在蟒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-31 15:56:22 p00ya

这不会给所有可能性。给出的例子只会给出4个结果，当应该有20个。 – interjay 2010-05-31 16:22:35

啊，对。应该是+ numzeroes不+ 1.修正了现在，len（列表（intersperse（x，3）））= 20. – p00ya 2010-05-31 16:32:09

谢谢一堆:) y.insert（0，i）应该是y.insert（i，0 ），但其他方面效果很好。再次感谢。 – 2010-05-31 16:42:13

一个提示：如果有Ž零和叔列表然后你描述的组合的数量是choose（Z + T，Z）。（stars and bars技巧将有助于明白这是为什么。）

要生成这些组合，您可以生成{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-31 16:11:00 dreeves

我d做类似......的东西：

>>> 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-31 16:25:22

生成具有某种约束的所有排列

回答

相关问题