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

## 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?

• 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.
• @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)!
• 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.
• @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.)

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!

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)



52 people think this answer is useful

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

from itertools import compress, product

def combinations(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'}]



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)



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']



34 people think this answer is useful

This one-liner 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

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]]



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



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] ,

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)]



8 people think this answer is useful

Here is yet another solution (one-liner), 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)]



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']
]



6 people think this answer is useful

3 functions:

1. all combinations of n elements list
2. all combinations of n elements list where order is not distinct
3. 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:], n-1):
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], n-1):
yield [a[i]] + x

if __name__ == "__main__":
for s in combinations(list(map(int, sys.argv[2:])), int(sys.argv[1])):
print(s)



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



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



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

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)]



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
#  3-item 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 2-items 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[index-1]:        # 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()



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']))



2 people think this answer is useful

def comb(s, res):
if not s: return
for i in range(0, len(s)):
t = s[0:i] + s[i + 1:]
comb(t, res)

res = set()
comb('game', res)

print(res)



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

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 = "".

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



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']



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[j-1] + 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



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)



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



-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')