Making all possible combinations of a list

Simply use itertools.combinations. For example:

import itertoolslst = [1, 2, 3]combs = []for i in xrange(1, len(lst)+1):    combs.append(i)    els = [list(x) for x in itertools.combinations(lst, i)]    combs.append(els)

Now combs holds this value:

[1, [[1], [2], [3]], 2, [[1, 2], [1, 3], [2, 3]], 3, [[1, 2, 3]]]

Yes, it's slightly different from the sample output you provided, but in that output you weren't listing all possible combinations.

I'm listing the size of the combination before the actual list for each size, if what you need is simply the combinations (without the size, as it appears in your sample output) then try these other version of the code:

import itertoolslst = [1, 2, 3]combs = []for i in xrange(1, len(lst)+1):    els = [list(x) for x in itertools.combinations(lst, i)]    combs.extend(els)

Now combs holds this value:

[[1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]]

The itertools module indeed returns generators instead of lists, but:

• Generators are often more efficient than lists (especially if you are generating a large number of combinations)
• You can always convert generators to lists using list(...) when you really need to.

The chain and combinations functions of itertools work well, but you need to use Python 2.6 or greater:

import itertoolsdef all_combinations(any_list):    return itertools.chain.from_iterable(        itertools.combinations(any_list, i + 1)        for i in xrange(len(any_list)))

You can then call this as such:

# as a generatorall_combinations([1,2,3])  # --> <itertools.chain at 0x10ef7ce10># as a listlist(all_combinations([1,2,3]))  # --> [(1,), (2,), (3,), (1, 2), (1, 3), (2, 3), (1, 2, 3)]# as a list of lists[list(l) for l in all_combinations([1,2,3])]  # --> [[1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]]

If you haven't used generators before, note that you loop through them as if they were a list, such as this:

# a generator returned instead of listmy_combinations = all_combinations([1,2,3])# this would also work if `my_combinations` were a listfor c in my_combinations:    print "Combo", c"""Prints:  Combo (1,)  Combo (2,)  Combo (3,)  Combo (1, 2)  Combo (1, 3)  Combo (2, 3)  Combo (1, 2, 3)"""

The performance difference can be dramatic. If you compare the performance you'll see that the generator is much faster to create:

# as a generatorall_combinations(range(25))  # timing: 100000 loops, best of 3: 2.53 µs per loop# as a listlist(all_combinations(range(25)))  # timing: 1 loops, best of 3: 9.37 s per loop

Note that it would still take some time to iterate through all the combinations in either case, but it can be a big win for you especially if you find what you're looking for early on.

The functions from the itertools module return iterators. All you need to do to convert these into lists is call list() on the result.

However, since you will need to call itertools.combinations three separate times (once for each different length), you can just use list.extend to add all elements of the iterator to your final list.

Try the following:

import itertoolsin_list = [1, 2, 3]out_list = []for i in range(1, len(in_list)+1):    out_list.extend(itertools.combinations(in_list, i))

Or as a list comprehension:

out_list = [c for i in range(len(in_list)) for c in itertools.combinations(in_list, i+1)]

These will result in the following list:

[(1,), (2,), (3,), (1, 2), (1, 3), (2, 3), (1, 2, 3)]

If you want lists instead of tuples, and to convert the single length tuples to just the value, you can do the following:

out_list = [x[0] if len(x) == 1 else list(x) for x in out_list]# [1, 2, 3, [1, 2], [1, 3], [2, 3], [1, 2, 3]]

Or to leave the single items as lists:

out_list = map(list, out_list)