Генерация всех перестановок с родом ограничением

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

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

Answer 2

Один намек: Если есть Z нули и списки т, то число комбинаций вы описываете choose (г + т, г). (stars and bars трюк поможет понять, почему это правда.)

Чтобы сгенерировать эти комбинации, вы можете сгенерировать все подмножества длины-z из {1, ..., z + t}. Каждый из них дал бы позиции нулей.

Еще лучше, вот обобщение Вашего вопроса:

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

Ваш вход х может быть преобразована в форму, у подходящего для вышеупомянутого обобщения следующим образом:

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

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

Может быть Конечно, микро-оптимизировано, но я надеюсь, что общая идея понятна: определить весь набор индексов, которые могут иметь нули, и поместить ненулевые элементы исходного списка в другие места по порядку.