Generating all possible combinations of a list, “itertools.combinations” misses some results

Each Answer to this Q is separated by one/two green lines.

Given a list of items in Python, how can I get all the possible combinations of the items?

There are several similar questions on this site, that suggest using itertools.combinations, but that returns only a subset of what I need:

stuff = [1, 2, 3]
for L in range(0, len(stuff)+1):
    for subset in itertools.combinations(stuff, L):
        print(subset)

()
(1,)
(2,)
(3,)
(1, 2)
(1, 3)
(2, 3)
(1, 2, 3)

As you see, it returns only items in a strict order, not returning (2, 1), (3, 2), (3, 1), (2, 1, 3), (3, 1, 2), (2, 3, 1), and (3, 2, 1). Is there some workaround for that? I can’t seem to come up with anything.

Use itertools.permutations:

>>> import itertools
>>> stuff = [1, 2, 3]
>>> for L in range(0, len(stuff)+1):
        for subset in itertools.permutations(stuff, L):
                print(subset)
...         
()
(1,)
(2,)
(3,)
(1, 2)
(1, 3)
(2, 1)
(2, 3)
(3, 1)
....

Help on itertools.permutations:

permutations(iterable[, r]) --> permutations object

Return successive r-length permutations of elements in the iterable.

permutations(range(3), 2) --> (0,1), (0,2), (1,0), (1,2), (2,0), (2,1)

You can generate all the combinations of a list in python using this simple code

import itertools

a = [1,2,3,4]
for i in xrange(1,len(a)+1):
   print list(itertools.combinations(a,i))

Result:

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

Are you looking for itertools.permutations instead?

From help(itertools.permutations),

Help on class permutations in module itertools:

class permutations(__builtin__.object)
 |  permutations(iterable[, r]) --> permutations object
 |  
 |  Return successive r-length permutations of elements in the iterable.
 |  
 |  permutations(range(3), 2) --> (0,1), (0,2), (1,0), (1,2), (2,0), (2,1)

Sample Code :

>>> from itertools import permutations
>>> stuff = [1, 2, 3]
>>> for i in range(0, len(stuff)+1):
        for subset in permutations(stuff, i):
               print(subset)


()
(1,)
(2,)
(3,)
(1, 2)
(1, 3)
(2, 1)
(2, 3)
(3, 1)
(3, 2)
(1, 2, 3)
(1, 3, 2)
(2, 1, 3)
(2, 3, 1)
(3, 1, 2)
(3, 2, 1)

From Wikipedia, the difference between permutations and combinations :

Permutation :

Informally, a permutation of a set of objects is an arrangement of those objects into a particular order. For example, there are six permutations of the set {1,2,3}, namely (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), and (3,2,1).

Combination :

In mathematics a combination is a way of selecting several things out of a larger group, where (unlike permutations) order does not matter.

itertools.permutations is going to be what you want. By mathematical definition, order does not matter for combinations, meaning (1,2) is considered identical to (2,1). Whereas with permutations, each distinct ordering counts as a unique permutation, so (1,2) and (2,1) are completely different.

Here is a solution without itertools

First lets define a translation between an indicator vector of 0 and 1s and a sub-list (1 if the item is in the sublist)

def indicators2sublist(indicators,arr):
   return [item for item,indicator in zip(arr,indicators) if int(indicator)==1]

Next, Well define a mapping from a number between 0 and 2^n-1 to the its binary vector representation (using string’s format function) :

def bin(n,sz):
   return ('{d:0'+str(sz)+'b}').format(d=n)

All we have left to do, is to iterate all the possible numbers, and call indicators2sublist

def all_sublists(arr):
  sz=len(arr)
  for n in xrange(0,2**sz):
     b=bin(n,sz)
     yield indicators2sublist(b,arr)

I assume you want all possible combinations as ‘sets’ of values. Here is a piece of code that I wrote that might help give you an idea:

def getAllCombinations(object_list):
    uniq_objs = set(object_list)
    combinations = []
    for obj in uniq_objs:
        for i in range(0,len(combinations)):
            combinations.append(combinations[i].union([obj]))
        combinations.append(set([obj]))
return combinations

Here is a sample:

combinations = getAllCombinations([20,10,30])
combinations.sort(key = lambda s: len(s))
print combinations
... [set([10]), set([20]), set([30]), set([10, 20]), set([10, 30]), set([20, 30]), set([10, 20, 30])]

I think this has n! time complexity, so be careful. This works but may not be most efficient

just thought i’d put this out there since i couldn’t fine EVERY possible outcome and keeping in mind i only have the rawest most basic of knowledge when it comes to python and there’s probably a much more elegant solution…(also excuse the poor variable names

testing = [1, 2, 3]

testing2= [0]

n = -1

def testingSomethingElse(number):

try:

    testing2[0:len(testing2)] == testing[0]

    n = -1

    testing2[number] += 1

except IndexError:

    testing2.append(testing[0])

while True:

n += 1

testing2[0] = testing[n]

print(testing2)

if testing2[0] == testing[-1]:

    try:

        n = -1

        testing2[1] += 1

    except IndexError:

        testing2.append(testing[0])

    for i in range(len(testing2)):

        if testing2[i] == 4:

            testingSomethingElse(i+1)

            testing2[i] = testing[0]

i got away with == 4 because i’m working with integers but you may have to modify that accordingly…


The answers/resolutions are collected from stackoverflow, are licensed under cc by-sa 2.5 , cc by-sa 3.0 and cc by-sa 4.0 .