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
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
 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
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
 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
Here’s a lazy oneliner, 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(...)
onitems
(workaround: ifitems
is something like an iterable like a generator, turn it into a list first withitems=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: usecollections.Counter
as a dropin replacement forset
; it’s basically a multiset… though you may need to later usetuple(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
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)!
Feb 11, 2020 at 6:02
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.
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
