Python all combinations of a list of lists

Question

So I have a list of lists of strings

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

and I want to get all possible combinations, such that the result is

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

So far I have come up with this code snippet

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

largely following an answer in this post.

But that results in

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

and I am currently stumped, trying to find an elegant, pythonic way to unpack those tuples.

Anand S Kumar · Accepted Answer · 2015-10-14T18:50:20.703

7

You can use itertools.chain.from_iterable to flatten the tuple of lists into a list. Example -

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)

Demo -

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

edited Oct 14 '15 at 18:50

answered Oct 14 '15 at 16:00

Anand S Kumar

88,551
18
188
176

1

Nice. I am often amazed at how powerful `itertools` is. – John Coleman Oct 14 '15 at 16:02
Perfect. Exactly what I was looking for. Thanks! – Matt M. Oct 14 '15 at 16:10

Thomas Baruchel · Answer 2 · 2015-10-14T16:31:06.747

One idea for such a goal is to map integers from [0..2**n-1] where n is the number of sublists to all your target element according to a very simple rule: Take the element of index k if (2**k)&i!=0 where i runs over [0..2**n-1]. In other word, i has to be read bitwise, and for each bit set, the corresponding element from l is kept. From a mathematical point of view it is one of the cleanest way of achieving what you want to do since it follows very closely the definition of the parts of a set (where you have exactly 2**n parts for a set with n elements).

Not tried but something like that should work:

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)

If you don't want the empty list, just replace the relevant line with:

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

score 0 · Answer 3 · answered Oct 14 '15 at 16:36

0

If you want all combinations, you may consider this simple way:

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

answered Oct 14 '15 at 16:36

Fei Yuan

82
5

If the original list contained 4 lists, this would not contain the resulting combinations of length 3, though. – Matt M. Oct 14 '15 at 16:42
@Matt M. Yes, you are right, I did not consider the list contains 4 lists, only show a simple case. in case of more than 3 lists, Anand S Kumar's method will be the one you need. Thank you for letting me know. – Fei Yuan Oct 14 '15 at 16:49

B. M. · Answer 4 · 2015-10-14T20:12:40.347

0

With comprehension lists :

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

edited Oct 14 '15 at 20:12

answered Oct 14 '15 at 18:47

B. M.

18,243
2
35
54

Python all combinations of a list of lists

4 Answers4