Making all possible combinations of a list [duplicate]

Question

I need to be able to make a list that contains all possible combinations of an inputted list. For example the list [1,2,3] should return [1 [1,2] [1,3] 2 [2,3] 3 [1,2,3]] The list doesn't have to be in any particular order. On this site I've found lots of functions using the itertools but those are returning objects when I need just a list.

Whencesoever

Does this answer your question? How to get all possible combinations of a list’s elements? – Weitzman

Answer 1

Simply use itertools.combinations. For example:

import itertools

lst = [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 itertools

lst = [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]]

Mange

this is not what the OP asked. – Joycelynjoye

@julio.alegria yes, that's what the OP asked, I just edited my answer – Darvon

That works great and returns close to what I'm looking for. Is there any way to get a list of lists instead of tuples? – Whencesoever

@Charles, I just edited my answer, I believe now it's what you were asking. Don't let the downvotes fool you :) they were cast before I had time for expanding my first answer – Darvon

In the itertools.combinations(l,i) section of the code, where does the l come from? I'm assuming that's the lowercase L and not a 1. – Whencesoever

You're welcome! please consider accepting the answer :) (marking the check to the left of the question, indicating that it's correct) – Darvon

like I told you, the downvote is for the answer before you edited, so I'm guessing it is because you misread the question. – Joycelynjoye

@julio.alegria de acuerdo, pero es costumbre (o al menos yo lo hago) que después de que alguien arregla una respuesta incorrecta, el downvote se quita haciendo click nuevamente en la flecha – Darvon

I don't understand why @Joycelynjoye downvoted this, very rude! Answer was incorrect to begin with but Oscar fixed the answer and it works now. Remove the downvote. Elegant and concise solution! +1 :) – Fazio

Answer 2

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 itertools

def 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 generator
all_combinations([1,2,3])  # --> <itertools.chain at 0x10ef7ce10>

# as a list
list(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 list
my_combinations = all_combinations([1,2,3])

# this would also work if `my_combinations` were a list
for 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 generator
all_combinations(range(25))  # timing: 100000 loops, best of 3: 2.53 µs per loop

# as a list
list(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.

Constitutive

This should be the accepted answer. It might be more difficult to follow, but it is the most efficient use of generators that you're going to find. Much more memory efficient for large lists. – Breadwinner

Answer 3

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 itertools
in_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)

Hissing

I tried using this but the interpreter said I can't use iter on NoneTypes. – Whencesoever

both of your solutions are still returning a list of tuples. – Joycelynjoye

Yeah i need a list of lists, not tuples. Is there a way to solve the problem without using the itertools? – Whencesoever

@Charles, you can solve it without itertools but it'll be way harder. Converting tuples to lists is really easy, and tuples are almost exactly the same as lists so I doubt you really need to. If you getting an error, then show us the code that didn't work. We can't figure out what you did wrong otherwise. – Sullage

@Charles - Edited my code for converting from tuples to lists, and also for converting single length tuples to just the value as it is in your example. This can be done without itertools but it won't be as concise. – Hissing

In the documentation for itertools there is an implementation of combinations that does not use any itertools functions. – Hissing

Found the error. It was just a mistake on my part when trying to work the code into a function. Thank you for the help. – Whencesoever

Answer 4

You could solve your problem using itertools.combinations inside of a loop:

>>> l = [1,2,3]
>>> comb = []
>>> for i in range(len(l)):
...   comb += itertools.combinations(l,i+1)
... 
>>> comb
[(1,), (2,), (3,), (1, 2), (1, 3), (2, 3), (1, 2, 3)]

And if you want them as a list:

>>> comb_list = [ list(t) for t in comb ]
>>> comb_list
[[1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]]

EDIT: The first parameter of combinations is the iterable and the second one is the length of the resulting tuples (in this case, going from 1 to len(l)).

More about combinations: http://docs.python.org/library/itertools.html#itertools.combinations

Joycelynjoye

Answer 5

l = [1,2,3]
combs = reduce(lambda x, y: list(itertools.combinations(l, y)) + x, range(len(l)+1), [])

If you want a oneliner.

Queasy

Answer 6

I think it's worth boiling down the other answers here into a simple Python 3 example:

from itertools import chain, combinations

def all_combinations(array):
    return chain(*(list(combinations(array, i + 1)) for i in range(len(array))))

This returns an iterable, to view the values:

>>> print(list(all_combinations((1, 2, 3))))
[(1,), (2,), (3,), (1, 2), (1, 3), (2, 3), (1, 2, 3)]

Psalterium