生成具有某種約束的所有排列

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

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

生成具有某種約束的所有排列

回答

相關問題