Python все комбинации списка списков

Итак, у меня есть список списков строк 

[['a','b'],['c','d'],['e','f']]

И я хочу получить все возможные комбинации, такие что результат будет 

[['a','b'],['c','d'],['e','f'],
 ['a','b','c','d'],['a','b','e','f'],['c','d','e','f'],
 ['a','b','c','d','e','f']]

До сих пор я придумал этот фрагмент кода 

input = [['a','b'],['c','d'],['e','f']]
combs = []
for i in xrange(1, len(input)+1):
    els = [x for x in itertools.combinations(input, i)]
    combs.extend(els)
print combs

В основном после ответа в этом посте.

Но это приводит к 

[(['a','b'],),(['c','d'],),(['e','f'],),
 (['a','b'],['c','d']),(['a','b'],['e','f']),(['c','d'],['e','f']),
 (['a','b'],['c', 'd'],['e', 'f'])]
И в настоящее время я в тупике, пытаясь найти элегантный, питонский способ распаковать эти кортежи.
4 5
python list tuples combinations itertools

4 ответа:

Вы можете использовать itertools.chain.from_iterable чтобы сгладить кортеж списков в список. Пример - 

import itertools
input = [['a','b'],['c','d'],['e','f']]
combs = []
for i in xrange(1, len(input)+1):
    els = [list(itertools.chain.from_iterable(x)) for x in itertools.combinations(input, i)]
    combs.extend(els)

Демо - 

>>> import itertools
>>> input = [['a','b'],['c','d'],['e','f']]
>>> combs = []
>>> for i in range(1, len(input)+1):
...     els = [list(itertools.chain.from_iterable(x)) for x in itertools.combinations(input, i)]
...     combs.extend(els)
...
>>> import pprint
>>> pprint.pprint(combs)
[['a', 'b'],
 ['c', 'd'],
 ['e', 'f'],
 ['a', 'b', 'c', 'd'],
 ['a', 'b', 'e', 'f'],
 ['c', 'd', 'e', 'f'],
 ['a', 'b', 'c', 'd', 'e', 'f']]
6

Одна из идей для такой цели состоит в том, чтобы сопоставить целые числа из [0..2**n-1] , где n-число подсписков, всем вашим целевым элементам согласно очень простому правилу: Возьмем элемент индекса k, если (2**k)&i!=0, где i перебегает [0..2**n-1]. Другими словами, i должен быть прочитан побитово, и для каждого набора битов сохраняется соответствующий элемент из l. С математической точки зрения это один из самых чистых способов достижения того, что вы хотите сделать, так как он очень точно следует определению частей множества (где у вас есть ровно 2**n частей для множества с n элементами).

Не пробовал, но что-то вроде этого должно сработать: 

l = [['a','b'],['c','d'],['e','f']]                                                    
n = len(l)
output = []
for i in range(2**n):
    s = []
    for k in range(n):
        if (2**k)&i: s = s + l[k]
    output.append(s)

Если вам не нужен пустой список, просто замените соответствующую строку на: 

for i in range(1,2**n):
0

Если вы хотите все комбинации, вы можете рассмотреть этот простой способ: 

import itertools

a = [['a','b'],['c','d'],['e','f']]
a = a + [i + j for i in a for j in a if i != j] + [list(itertools.chain.from_iterable(a))]
0

Со списками понимания: 

combs=[sum(x,[]) for i in range(len(l)) for x in itertools.combinations(l,i+1)]
0