Categories
combinations python

How to get all possible combinations of a list’s elements?

627

I have a list with 15 numbers in, and I need to write some code that produces all 32,768 combinations of those numbers.

I’ve found some code (by Googling) that apparently does what I’m looking for, but I found the code fairly opaque and am wary of using it. Plus I have a feeling there must be a more elegant solution.

The only thing that occurs to me would be to just loop through the decimal integers 1–32768 and convert those to binary, and use the binary representation as a filter to pick out the appropriate numbers.

Does anyone know of a better way? Using map(), maybe?

5

  • 17

    Readers should note that whether the list items are unique is an extremely important consideration, as many algorithms will then overcount some subset (e.g. ‘abccc’ -> [”, ‘a’, ‘b’, ‘c’, ‘c’, ‘c’, ‘ac’, ‘ac’, ‘ac’, …]. An easy workaround is to just shove all elements in a set before getting their permutations.

    Sep 14, 2015 at 0:23

  • @ninjagecko Using the Set library is not efficient as each are O(n) at the best. Thus adding n functions to a set is actually O(n^2)!

    – SMBiggs

    Feb 11, 2020 at 6:02

  • 3

    From carefully reading the question, it seems that the OP is asking for the PowerSet of his list of 15 numbers, not all the combinations. I think this may be why the answers are all over the place.

    – SMBiggs

    Feb 11, 2020 at 6:53

  • @Scott Biggs: are you sure you’re taking about Python here? Set insertions and lookups are O(1) average case. They’re like dictionaries. They use hashing. Python doesn’t have a special set library (it’s in the standard library). We’re inserting numbers here not functions. (It would still be inefficient to use O(2^n) memory; the proper solution for people who want combinations rather than the powerset is a simple recursive implementation, or product, etc.)

    Feb 12, 2020 at 9:36

  • See also stackoverflow.com/questions/10342939/… .

    Nov 16, 2021 at 22:20

641

Have a look at itertools.combinations:

itertools.combinations(iterable, r)

Return r length subsequences of elements from
the input iterable.

Combinations are emitted in lexicographic sort order. So, if the
input iterable is sorted, the
combination tuples will be produced in
sorted order.

Since 2.6, batteries are included!

4

  • 49

    you can just list it all. list(itertools.combinations(iterable, r))

    – silgon

    Sep 14, 2017 at 12:23

  • 24

    is there anything that does not require r, i.e. combinations of any length subsequences of elements.

    May 23, 2020 at 5:39

  • 3

    this is very good and pointed me to what really solved my problem, which was itertools.combination_with_replacement.

    Oct 15, 2020 at 23:39


  • 3

    the function writes intertools.combinations_with_replacement

    Sep 3, 2021 at 17:53

641

Have a look at itertools.combinations:

itertools.combinations(iterable, r)

Return r length subsequences of elements from
the input iterable.

Combinations are emitted in lexicographic sort order. So, if the
input iterable is sorted, the
combination tuples will be produced in
sorted order.

Since 2.6, batteries are included!

4

  • 49

    you can just list it all. list(itertools.combinations(iterable, r))

    – silgon

    Sep 14, 2017 at 12:23

  • 24

    is there anything that does not require r, i.e. combinations of any length subsequences of elements.

    May 23, 2020 at 5:39

  • 3

    this is very good and pointed me to what really solved my problem, which was itertools.combination_with_replacement.

    Oct 15, 2020 at 23:39


  • 3

    the function writes intertools.combinations_with_replacement

    Sep 3, 2021 at 17:53

63

Here’s a lazy one-liner, also using itertools:

from itertools import compress, product

def combinations(items):
    return ( set(compress(items,mask)) for mask in product(*[[0,1]]*len(items)) )
    # alternative:                      ...in product([0,1], repeat=len(items)) )

Main idea behind this answer: there are 2^N combinations — same as the number of binary strings of length N. For each binary string, you pick all elements corresponding to a “1”.

items=abc * mask=###
 |
 V
000 -> 
001 ->   c
010 ->  b
011 ->  bc
100 -> a
101 -> a c
110 -> ab
111 -> abc

Things to consider:

  • This requires that you can call len(...) on items (workaround: if items is something like an iterable like a generator, turn it into a list first with items=list(_itemsArg))
  • This requires that the order of iteration on items is not random (workaround: don’t be insane)
  • This requires that the items are unique, or else {2,2,1} and {2,1,1} will both collapse to {2,1} (workaround: use collections.Counter as a drop-in replacement for set; it’s basically a multiset… though you may need to later use tuple(sorted(Counter(...).elements())) if you need it to be hashable)

Demo

>>> list(combinations(range(4)))
[set(), {3}, {2}, {2, 3}, {1}, {1, 3}, {1, 2}, {1, 2, 3}, {0}, {0, 3}, {0, 2}, {0, 2, 3}, {0, 1}, {0, 1, 3}, {0, 1, 2}, {0, 1, 2, 3}]

>>> list(combinations('abcd'))
[set(), {'d'}, {'c'}, {'c', 'd'}, {'b'}, {'b', 'd'}, {'c', 'b'}, {'c', 'b', 'd'}, {'a'}, {'a', 'd'}, {'a', 'c'}, {'a', 'c', 'd'}, {'a', 'b'}, {'a', 'b', 'd'}, {'a', 'c', 'b'}, {'a', 'c', 'b', 'd'}]

0