The Question :
478 people think this question is useful
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?
The Question Comments :
The Answer 1
518 people think this answer is useful
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!
The Answer 2
665 people think this answer is useful
This answer missed one aspect: the OP asked for ALL combinations… not just combinations of length “r”.
So you’d either have to loop through all lengths “L”:
import itertools
stuff = [1, 2, 3]
for L in range(0, len(stuff)+1):
for subset in itertools.combinations(stuff, L):
print(subset)
Or — if you want to get snazzy (or bend the brain of whoever reads your code after you) — you can generate the chain of “combinations()” generators, and iterate through that:
from itertools import chain, combinations
def all_subsets(ss):
return chain(*map(lambda x: combinations(ss, x), range(0, len(ss)+1)))
for subset in all_subsets(stuff):
print(subset)
The Answer 3
52 people think this answer is useful
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(...)
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 dropin 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'}]
The Answer 4
48 people think this answer is useful
In comments under the highly upvoted answer by @Dan H, mention is made of the powerset()
recipe in the itertools
documentation—including one by Dan himself. However, so far no one has posted it as an answer. Since it’s probably one of the better if not the best approach to the problem—and given a little encouragement from another commenter, it’s shown below. The function produces all unique combinations of the list elements of every length possible (including those containing zero and all the elements).
Note: If the, subtly different, goal is to obtain only combinations of unique elements, change the line s = list(iterable)
to s = list(set(iterable))
to eliminate any duplicate elements. Regardless, the fact that the iterable
is ultimately turned into a list
means it will work with generators (unlike several of the other answers).
from itertools import chain, combinations
def powerset(iterable):
"powerset([1,2,3]) > () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
s = list(iterable) # allows duplicate elements
return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))
stuff = [1, 2, 3]
for i, combo in enumerate(powerset(stuff), 1):
print('combo #{}: {}'.format(i, combo))
Output:
combo #1: ()
combo #2: (1,)
combo #3: (2,)
combo #4: (3,)
combo #5: (1, 2)
combo #6: (1, 3)
combo #7: (2, 3)
combo #8: (1, 2, 3)
The Answer 5
38 people think this answer is useful
Here is one using recursion:
>>> import copy
>>> def combinations(target,data):
... for i in range(len(data)):
... new_target = copy.copy(target)
... new_data = copy.copy(data)
... new_target.append(data[i])
... new_data = data[i+1:]
... print new_target
... combinations(new_target,
... new_data)
...
...
>>> target = []
>>> data = ['a','b','c','d']
>>>
>>> combinations(target,data)
['a']
['a', 'b']
['a', 'b', 'c']
['a', 'b', 'c', 'd']
['a', 'b', 'd']
['a', 'c']
['a', 'c', 'd']
['a', 'd']
['b']
['b', 'c']
['b', 'c', 'd']
['b', 'd']
['c']
['c', 'd']
['d']
The Answer 6
34 people think this answer is useful
This oneliner gives you all the combinations (between 0
and n
items if the original list/set contains n
distinct elements) and uses the native method itertools.combinations
:
Python 2
from itertools import combinations
input = ['a', 'b', 'c', 'd']
output = sum([map(list, combinations(input, i)) for i in range(len(input) + 1)], [])
Python 3
from itertools import combinations
input = ['a', 'b', 'c', 'd']
output = sum([list(map(list, combinations(input, i))) for i in range(len(input) + 1)], [])
The output will be:
[[],
['a'],
['b'],
['c'],
['d'],
['a', 'b'],
['a', 'c'],
['a', 'd'],
['b', 'c'],
['b', 'd'],
['c', 'd'],
['a', 'b', 'c'],
['a', 'b', 'd'],
['a', 'c', 'd'],
['b', 'c', 'd'],
['a', 'b', 'c', 'd']]
Try it online:
http://ideone.com/COghfX
The Answer 7
24 people think this answer is useful
This is an approach that can be easily transfered to all programming languages supporting recursion (no itertools, no yield, no list comprehension):
def combs(a):
if len(a) == 0:
return [[]]
cs = []
for c in combs(a[1:]):
cs += ]]
return cs
>>> combs([1,2,3,4,5])
[[], [1], [2], [2, 1], [3], [3, 1], [3, 2], ..., [5, 4, 3, 2, 1]]
The Answer 8
21 people think this answer is useful
I agree with Dan H that Ben indeed asked for all combinations. itertools.combinations()
does not give all combinations.
Another issue is, if the input iterable is big, it is perhaps better to return a generator instead of everything in a list:
iterable = range(10)
for s in xrange(len(iterable)+1):
for comb in itertools.combinations(iterable, s):
yield comb
The Answer 9
15 people think this answer is useful
I thought I would add this function for those seeking an answer without importing itertools or any other extra libraries.
def powerSet(items):
"""
Power set generator: get all possible combinations of a list’s elements
Input:
items is a list
Output:
returns 2**n combination lists one at a time using a generator
Reference: edx.org 6.00.2x Lecture 2  Decision Trees and dynamic programming
"""
N = len(items)
# enumerate the 2**N possible combinations
for i in range(2**N):
combo = []
for j in range(N):
# test bit jth of integer i
if (i >> j) % 2 == 1:
combo.append(items[j])
yield combo
Simple Yield Generator Usage:
for i in powerSet([1,2,3,4]):
print (i, ", ", end="")
Output from Usage example above:
[] , [1] , [2] , [1, 2] , [3] , [1, 3] , [2, 3] , [1, 2, 3] , [4] ,
[1, 4] , [2, 4] , [1, 2, 4] , [3, 4] , [1, 3, 4] , [2, 3, 4] , [1, 2,
3, 4] ,
The Answer 10
14 people think this answer is useful
You can generating all combinations of a list in python using this simple code
import itertools
a = [1,2,3,4]
for i in xrange(0,len(a)+1):
print list(itertools.combinations(a,i))
Result would be :
[()]
[(1,), (2,), (3,), (4,)]
[(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)]
[(1, 2, 3), (1, 2, 4), (1, 3, 4), (2, 3, 4)]
[(1, 2, 3, 4)]
The Answer 11
8 people think this answer is useful
Here is yet another solution (oneliner), involving using the itertools.combinations
function, but here we use a double list comprehension (as opposed to a for loop or sum):
def combs(x):
return
Demo:
>>> combs([1,2,3,4])
[(),
(1,), (2,), (3,), (4,),
(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4),
(1, 2, 3), (1, 2, 4), (1, 3, 4), (2, 3, 4),
(1, 2, 3, 4)]
The Answer 12
8 people think this answer is useful
from itertools import permutations, combinations
features = ['A', 'B', 'C']
tmp = []
for i in range(len(features)):
oc = combinations(features, i + 1)
for c in oc:
tmp.append(list(c))
output
[
['A'],
['B'],
['C'],
['A', 'B'],
['A', 'C'],
['B', 'C'],
['A', 'B', 'C']
]
The Answer 13
6 people think this answer is useful
3 functions:
 all combinations of n elements list
 all combinations of n elements list where order is not distinct
 all permutations
import sys
def permutations(a):
return combinations(a, len(a))
def combinations(a, n):
if n == 1:
for x in a:
yield [x]
else:
for i in range(len(a)):
for x in combinations(a[:i] + a[i+1:], n1):
yield [a[i]] + x
def combinationsNoOrder(a, n):
if n == 1:
for x in a:
yield [x]
else:
for i in range(len(a)):
for x in combinationsNoOrder(a[:i], n1):
yield [a[i]] + x
if __name__ == "__main__":
for s in combinations(list(map(int, sys.argv[2:])), int(sys.argv[1])):
print(s)
The Answer 14
6 people think this answer is useful
You can also use the powerset function from the excellent more_itertools
package.
from more_itertools import powerset
l = [1,2,3]
list(powerset(l))
# [(), (1,), (2,), (3,), (1, 2), (1, 3), (2, 3), (1, 2, 3)]
We can also verify, that it meets OP’s requirement
from more_itertools import ilen
assert ilen(powerset(range(15))) == 32_768
The Answer 15
4 people think this answer is useful
Below is a “standard recursive answer”, similar to the other similar answer https://stackoverflow.com/a/23743696/711085 . (We don’t realistically have to worry about running out of stack space since there’s no way we could process all N! permutations.)
It visits every element in turn, and either takes it or leaves it (we can directly see the 2^N cardinality from this algorithm).
def combs(xs, i=0):
if i==len(xs):
yield ()
return
for c in combs(xs,i+1):
yield c
yield c+(xs[i],)
Demo:
>>> list( combs(range(5)) )
[(), (0,), (1,), (1, 0), (2,), (2, 0), (2, 1), (2, 1, 0), (3,), (3, 0), (3, 1), (3, 1, 0), (3, 2), (3, 2, 0), (3, 2, 1), (3, 2, 1, 0), (4,), (4, 0), (4, 1), (4, 1, 0), (4, 2), (4, 2, 0), (4, 2, 1), (4, 2, 1, 0), (4, 3), (4, 3, 0), (4, 3, 1), (4, 3, 1, 0), (4, 3, 2), (4, 3, 2, 0), (4, 3, 2, 1), (4, 3, 2, 1, 0)]
>>> list(sorted( combs(range(5)), key=len))
[(),
(0,), (1,), (2,), (3,), (4,),
(1, 0), (2, 0), (2, 1), (3, 0), (3, 1), (3, 2), (4, 0), (4, 1), (4, 2), (4, 3),
(2, 1, 0), (3, 1, 0), (3, 2, 0), (3, 2, 1), (4, 1, 0), (4, 2, 0), (4, 2, 1), (4, 3, 0), (4, 3, 1), (4, 3, 2),
(3, 2, 1, 0), (4, 2, 1, 0), (4, 3, 1, 0), (4, 3, 2, 0), (4, 3, 2, 1),
(4, 3, 2, 1, 0)]
>>> len(set(combs(range(5))))
32
The Answer 16
3 people think this answer is useful
Here are two implementations of itertools.combinations
One that returns a list
def combinations(lst, depth, start=0, items=[]):
if depth <= 0:
return [items]
out = []
for i in range(start, len(lst)):
out += combinations(lst, depth  1, i + 1, items + [lst[i]])
return out
One returns a generator
def combinations(lst, depth, start=0, prepend=[]):
if depth <= 0:
yield prepend
else:
for i in range(start, len(lst)):
for c in combinations(lst, depth  1, i + 1, prepend + [lst[i]]):
yield c
Please note that providing a helper function to those is advised because the prepend argument is static and is not changing with every call
print(, 3)])
# [[1, 2, 3], [1, 2, 4], [1, 3, 4], [2, 3, 4]]
# get a hold of prepend
prepend = , 1)][0]
prepend.append(None)
print(, 3)])
# [[None, 1, 2, 3], [None, 1, 2, 4], [None, 1, 3, 4], [None, 2, 3, 4]]
This is a very superficial case but better be safe than sorry
The Answer 17
3 people think this answer is useful
I know it’s far more practical to use itertools to get the all the combinations, but you can achieve this partly with only list comprehension if you so happen to desire, granted you want to code a lot
For combinations of two pairs:
lambda l: [(a, b) for i, a in enumerate(l) for b in l[i+1:]]
And, for combinations of three pairs, it’s as easy as this:
lambda l: [(a, b, c) for i, a in enumerate(l) for ii, b in enumerate(l[i+1:]) for c in l[i+ii+2:]]
The result is identical to using itertools.combinations:
import itertools
combs_3 = lambda l: [
(a, b, c) for i, a in enumerate(l)
for ii, b in enumerate(l[i+1:])
for c in l[i+ii+2:]
]
data = ((1, 2), 5, "a", None)
print("A:", list(itertools.combinations(data, 3)))
print("B:", combs_3(data))
# A: [((1, 2), 5, 'a'), ((1, 2), 5, None), ((1, 2), 'a', None), (5, 'a', None)]
# B: [((1, 2), 5, 'a'), ((1, 2), 5, None), ((1, 2), 'a', None), (5, 'a', None)]
The Answer 18
2 people think this answer is useful
This code employs a simple algorithm with nested lists…
# FUNCTION getCombos: To generate all combos of an input list, consider the following sets of nested lists...
#
# [ [ [] ] ]
# [ [ [] ], [ [A] ] ]
# [ [ [] ], [ [A],[B] ], [ [A,B] ] ]
# [ [ [] ], [ [A],[B],[C] ], [ [A,B],[A,C],[B,C] ], [ [A,B,C] ] ]
# [ [ [] ], [ [A],[B],[C],[D] ], [ [A,B],[A,C],[B,C],[A,D],[B,D],[C,D] ], [ [A,B,C],[A,B,D],[A,C,D],[B,C,D] ], [ [A,B,C,D] ] ]
#
# There is a set of lists for each number of items that will occur in a combo (including an empty set).
# For each additional item, begin at the back of the list by adding an empty list, then taking the set of
# lists in the previous column (e.g., in the last list, for sets of 3 items you take the existing set of
# 3item lists and append to it additional lists created by appending the item (4) to the lists in the
# next smallest item count set. In this case, for the three sets of 2items in the previous list. Repeat
# for each set of lists back to the initial list containing just the empty list.
#
def getCombos(listIn = ['A','B','C','D','E','F'] ):
listCombos = [ [ [] ] ] # list of lists of combos, seeded with a list containing only the empty list
listSimple = [] # list to contain the final returned list of items (e.g., characters)
for item in listIn:
listCombos.append([]) # append an emtpy list to the end for each new item added
for index in xrange(len(listCombos)1, 0, 1): # set the index range to work through the list
for listPrev in listCombos[index1]: # retrieve the lists from the previous column
listCur = listPrev[:] # create a new temporary list object to update
listCur.append(item) # add the item to the previous list to make it current
listCombos[index].append(listCur) # list length and append it to the current list
itemCombo = '' # Create a str to concatenate list items into a str
for item in listCur: # concatenate the members of the lists to create
itemCombo += item # create a string of items
listSimple.append(itemCombo) # add to the final output list
return [listSimple, listCombos]
# END getCombos()
The Answer 19
2 people think this answer is useful
Without using itertools:
def combine(inp):
return combine_helper(inp, [], [])
def combine_helper(inp, temp, ans):
for i in range(len(inp)):
current = inp[i]
remaining = inp[i + 1:]
temp.append(current)
ans.append(tuple(temp))
combine_helper(remaining, temp, ans)
temp.pop()
return ans
print(combine(['a', 'b', 'c', 'd']))
The Answer 20
2 people think this answer is useful
How about this.. used a string instead of list, but same thing.. string can be treated like a list in Python:
def comb(s, res):
if not s: return
res.add(s)
for i in range(0, len(s)):
t = s[0:i] + s[i + 1:]
comb(t, res)
res = set()
comb('game', res)
print(res)
The Answer 21
2 people think this answer is useful
Combination from itertools
import itertools
col_names = ["aa","bb", "cc", "dd"]
all_combinations = itertools.chain(*[itertools.combinations(col_names,i+1) for i,_ in enumerate(col_names)])
print(list(all_combinations))
Thanks
The Answer 22
2 people think this answer is useful
Without itertools
in Python 3 you could do something like this:
def combinations(arr, carry):
for i in range(len(arr)):
yield carry + arr[i]
yield from combinations(arr[i + 1:], carry + arr[i])
where initially carry = "".
The Answer 23
2 people think this answer is useful
This is my implementation
def get_combinations(list_of_things):
"""gets every combination of things in a list returned as a list of lists
Should be read : add all combinations of a certain size to the end of a list for every possible size in the
the list_of_things.
"""
list_of_combinations = [list(combinations_of_a_certain_size)
for possible_size_of_combinations in range(1, len(list_of_things))
for combinations_of_a_certain_size in itertools.combinations(list_of_things,
possible_size_of_combinations)]
return list_of_combinations
The Answer 24
1 people think this answer is useful
Using list comprehension:
def selfCombine( list2Combine, length ):
listCombined = str( ['list2Combine[i' + str( i ) + ']' for i in range( length )] ).replace( "'", '' ) \
+ 'for i0 in range(len( list2Combine ) )'
if length > 1:
listCombined += str( [' for i' + str( i ) + ' in range( i' + str( i  1 ) + ', len( list2Combine ) )' for i in range( 1, length )] )\
.replace( "', '", ' ' )\
.replace( "['", '' )\
.replace( "']", '' )
listCombined = '[' + listCombined + ']'
listCombined = eval( listCombined )
return listCombined
list2Combine = ['A', 'B', 'C']
listCombined = selfCombine( list2Combine, 2 )
Output would be:
['A', 'A']
['A', 'B']
['A', 'C']
['B', 'B']
['B', 'C']
['C', 'C']
The Answer 25
0 people think this answer is useful
As stated in the documentation
def combinations(iterable, r):
# combinations('ABCD', 2) > AB AC AD BC BD CD
# combinations(range(4), 3) > 012 013 023 123
pool = tuple(iterable)
n = len(pool)
if r > n:
return
indices = list(range(r))
yield tuple(pool[i] for i in indices)
while True:
for i in reversed(range(r)):
if indices[i] != i + n  r:
break
else:
return
indices[i] += 1
for j in range(i+1, r):
indices[j] = indices[j1] + 1
yield tuple(pool[i] for i in indices)
x = [2, 3, 4, 5, 1, 6, 4, 7, 8, 3, 9]
for i in combinations(x, 2):
print i
The Answer 26
0 people think this answer is useful
I’m late to the party but would like to share the solution I found to the same issue:
Specifically, I was looking to do sequential combinations, so for “STAR” I wanted “STAR”, “TA”, “AR”, but not “SR”.
lst = [S, T, A, R]
lstCombos = []
for Length in range(0,len(lst)+1):
for i in lst:
lstCombos.append(lst[lst.index(i):lst.index(i)+Length])
Duplicates can be filtered with adding in an additional if before the last line:
lst = [S, T, A, R]
lstCombos = []
for Length in range(0,len(lst)+1):
for i in lst:
if not lst[lst.index(i):lst.index(i)+Length]) in lstCombos:
lstCombos.append(lst[lst.index(i):lst.index(i)+Length])
If for some reason this returns blank lists in the output, which happened to me, I added:
for subList in lstCombos:
if subList = '':
lstCombos.remove(subList)
The Answer 27
1 people think this answer is useful
If someone is looking for a reversed list, like I was:
stuff = [1, 2, 3, 4]
def reverse(bla, y):
for subset in itertools.combinations(bla, len(bla)y):
print list(subset)
if y != len(bla):
y += 1
reverse(bla, y)
reverse(stuff, 1)
The Answer 28
1 people think this answer is useful
flag = 0
requiredCals =12
from itertools import chain, combinations
def powerset(iterable):
s = list(iterable) # allows duplicate elements
return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))
stuff = [2,9,5,1,6]
for i, combo in enumerate(powerset(stuff), 1):
if(len(combo)>0):
#print(combo , sum(combo))
if(sum(combo)== requiredCals):
flag = 1
break
if(flag==1):
print('True')
else:
print('else')