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

311

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?

edited Oct 25 '16 at 16:20

martineau

69.3k1092186

asked Jan 21 '09 at 11:13

Ben

25.9k3276100

4

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
Sep 14 '15 at 0:23

add a comment |

311

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.

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

edited Oct 25 '16 at 16:20

martineau

69.3k1092186

asked Jan 21 '09 at 11:13

Ben

25.9k3276100

4

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
Sep 14 '15 at 0:23

add a comment |

311

111

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.

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

edited Oct 25 '16 at 16:20

martineau

69.3k1092186

asked Jan 21 '09 at 11:13

Ben

25.9k3276100

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.

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

python combinations

edited Oct 25 '16 at 16:20

martineau

69.3k1092186

asked Jan 21 '09 at 11:13

Ben

25.9k3276100

edited Oct 25 '16 at 16:20

martineau

69.3k1092186

asked Jan 21 '09 at 11:13

Ben

25.9k3276100

edited Oct 25 '16 at 16:20

martineau

69.3k1092186

edited Oct 25 '16 at 16:20

martineau

69.3k1092186

edited Oct 25 '16 at 16:20

martineau

69.3k1092186

asked Jan 21 '09 at 11:13

Ben

25.9k3276100

asked Jan 21 '09 at 11:13

Ben

25.9k3276100

asked Jan 21 '09 at 11:13

Ben

25.9k3276100

4

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
Sep 14 '15 at 0:23

add a comment |

4

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
Sep 14 '15 at 0:23

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
Sep 14 '15 at 0:23

add a comment |

24 Answers
24

active

oldest

votes

338

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!

edited Jan 21 '09 at 12:52

answered Jan 21 '09 at 11:20

James Brady

17.8k64455

2

I don't have python 2.6, but since that link contained the code for combinations, I was able to get it working. Thanks again!

– Ben
Jan 21 '09 at 11:38

Ah, yes - I didn't see that it was 2.6 only... updated my answer

– James Brady
Jan 21 '09 at 12:52

10

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

– silgon
Sep 14 '17 at 12:23

add a comment |

536

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)

edited May 1 '18 at 21:01

Steven C. Howell

4,26633562

answered May 5 '11 at 12:56

Dan H

7,93032328

29

Thanks for the support! In the weeks since I've posted the above reply, I've found that the NAME of the concept for what Ben is looking for is the "powerset" of the original set of 15 items. In fact, an example implementation is given on the standard python "itertools" doc page: docs.python.org/library/itertools.html (grep for "powerset").

– Dan H
Nov 16 '11 at 17:45

Alabaster's answer -- which answer are you referring to? Maybe its better to leave that reference out and concentrate on the question an your answer :)

– Wolf
Jul 21 '16 at 9:12

1

@wolf: Apparently either "Alabaster's answer" has been deleted or the user changed his name some time in the five years since I posted my answer. (I think "Alabaster" is now "James Brady".) I don't think it is unusual or against guidelines to discuss the strengths or weaknesses of other answers in one's own answer; it helps readers compare and contrast, IMO.

– Dan H
Jul 26 '16 at 13:02

16

For anyone reading this far: The powerset() generator function in the recipes section of the itertools documentation is simpler, potentially uses less memory, and is likely faster than the implementation shown here.

– martineau
Oct 25 '16 at 17:16

2

@martineau: Maybe post that as an answer?

– naught101
Dec 5 '16 at 22:42

|
show 7 more comments

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

edited Aug 11 '18 at 20:06

Greg

3,99111730

answered Jul 1 '11 at 0:21

ninjagecko

61.2k17113122

add a comment |

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)

edited Aug 1 '18 at 15:38

answered Dec 6 '16 at 1:45

martineau

69.3k1092186

add a comment |

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

answered May 19 '14 at 17:25

darxtrix

1,06711524

Can this be modified to return a list of lists instead of printing?

– James Vickery
Nov 9 '17 at 2:14

@JamesVickery yes, you could look at either making a list outside of the function and appending to that, or (better) make the function a generator, have a look at the 'yield' keyword :)

– Dangercrow
Nov 12 '17 at 14:01

new_data = copy.copy(data) - this row is redundant as far as I see, it doesn't influence on anything

– Dmitriy Fialkovskiy
Oct 25 '18 at 14:27

add a comment |

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

edited Feb 7 at 8:13

answered Jun 25 '14 at 7:08

Mathieu Rodic

4,88523140

This is a permutation

– AdHominem
Oct 28 '16 at 19:44

11

@AdHominem: no, it's not. It's a list of all combinations. Permutations would include, e.g. ['b', 'a'].

– naught101
Dec 5 '16 at 22:44

TypeError: can only concatenate list (not "map") to list

– 0x48piraj
Feb 6 at 0:28

@0x48piraj: thank you for noticing, I edited my answer consequently!

– Mathieu Rodic
Feb 7 at 8:14

add a comment |

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

answered Aug 24 '11 at 10:24

HongboZhu

2,92422128

1

Nice example. I love generators... and I love Python for having them! This example only has one combinations() object around at a time, and yields one of the combinations at time. (Perhaps you want to add the def block around this -- as a usage example.) Note that my implementation (with chain(), given above) is not too much worse: it's true that is creates all len(iterable) generators at once... but it does NOT create all 2 ** len(iterable) combinations at once, as -- to my understanding -- chain "uses up" the first generator before drawing from subsequent ones.

– Dan H
Nov 16 '11 at 17:54

add a comment |

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

edited Sep 14 '15 at 0:02

ninjagecko

61.2k17113122

answered Mar 17 '15 at 5:52

saimadhu.polamuri

2,45311518

Bug in this code: does not return the empty set. Might mean xrange(0, ...) but haven't tested. edit: I went ahead and edited your answer to fix it.

– ninjagecko
Sep 14 '15 at 0:01

add a comment |

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

answered Dec 20 '16 at 4:29

LectureMaker

1,20511115

add a comment |

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 [c for i in range(len(x)+1) for c in combinations(x,i)]

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

answered Sep 14 '15 at 0:13

ninjagecko

61.2k17113122

add a comment |

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

edited May 23 '17 at 12:10

Community♦

answered Sep 13 '15 at 23:28

ninjagecko

61.2k17113122

add a comment |

It could be done using itertools

For permutations

This method takes a list as an input and return an object list of tuples that contain permutation of length L in a list form.

# A Python program to print all  

# permutations of given length 

from itertools import permutations 



# Get all permutations of length 2 

# and length 2 

perm = permutations([1, 2, 3], 2) 



# Print the obtained permutations 

for i in list(perm): 

    print (i)

For Combination

This method takes a list and a input r as a input and return a object list of tuples which contain all possible combination of length r in a list form.

# A Python program to print all  

# combinations of given length 

from itertools import combinations 



# Get all combinations of [1, 2, 3] 

# and length 2 

comb = combinations([1, 2, 3], 2) 



# Print the obtained combinations 

for i in list(comb): 

    print (i)

see this

answered Sep 28 '18 at 13:30

Umer

753716

add a comment |

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

edited May 1 '15 at 13:34

Mattia Maestrini

25.9k146680

answered May 1 '15 at 5:07

TiPS

371

So what this code appears to do is return [listOfCombinations, listOfCombinationsGroupedBySize]. Unfortunately when run with the demo input it gives 63 elements rather than 64; it seems to be missing the empty set (in this case, the empty string "").

– ninjagecko
Sep 13 '15 at 23:58

add a comment |

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

edited Oct 7 '17 at 6:18

answered Oct 6 '17 at 16:08

Cynadyde

788

add a comment |

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

answered Oct 22 '17 at 0:57

Pradeep Vairamani

2,02422344

add a comment |

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

answered Dec 19 '17 at 16:23

Abhishek

1,10821434

add a comment |

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

answered Aug 21 '11 at 19:10

zmk

42866

3

This proposal is to do string mangling to build up sets?!?! Holy crow.... And: it is not returning the powerset, but rather, something like combinations_with_replacement(). (See docs.python.org/library/…)

– Dan H
Nov 16 '11 at 18:00

This indeed does the same as combination_with_replacement(), but at least on my box this runs slightly faster than itertools. What can I say, I like list comprehensions.

– zmk
Nov 24 '11 at 23:16

1

Thank you for the answer! What about create listCombined with reversed lists such as ['A', 'A'], ['A', 'B'], ['A', 'C'], ['B', 'A'], ['B', 'B'], ['B', 'C'], ['C', 'A'], ['C', 'B'] and ['C', 'C'] that include everything?

– Karyo
Mar 19 '15 at 10:55

add a comment |

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

answered Feb 5 '17 at 3:42

Andres Ulloa

311

What is your implementation solving better than the previous implementations posted here.

– user1767754
Jan 1 '18 at 22:47

add a comment |

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([c for c in combinations([1, 2, 3, 4], 3)])

# [[1, 2, 3], [1, 2, 4], [1, 3, 4], [2, 3, 4]]



# get a hold of prepend

prepend = [c for c in combinations(, -1)][0]

prepend.append(None)



print([c for c in combinations([1, 2, 3, 4], 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

edited Nov 6 '17 at 13:52

answered Nov 6 '17 at 9:01

Modar

113

add a comment |

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)

answered Dec 17 '17 at 18:04

Apurva Singh

1,8341427

add a comment |

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

answered Oct 12 '18 at 12:59

Laurynas Tamulevičius

702316

add a comment |

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 += [c, c+[a[0]]]

    return cs



>>> combs([1,2,3,4,5])

[, [1], [2], [2, 1], [3], [3, 1], [3, 2], ..., [5, 4, 3, 2, 1]]

edited Feb 8 at 22:24

answered Feb 1 at 13:02

Jonathan R

1,182512

add a comment |

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

answered May 7 '16 at 19:17

Anoop

874517

1

If I'm right, this is the exact code copied from python documentation [docs.python.org/3.6/library/itertools.html ]. If so, please do ref the source.

– GabrielChu
Dec 18 '17 at 9:33

interesting approach

– pelos
Nov 26 '18 at 22:47

add a comment |

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)

answered Dec 4 '17 at 6:54

Expat C

add a comment |

protected by Jean-François Fabre♦ Mar 9 '18 at 12:35

Thank you for your interest in this question.
Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

24 Answers
24

active

oldest

votes

24 Answers
24

active

oldest

votes

338

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!

edited Jan 21 '09 at 12:52

answered Jan 21 '09 at 11:20

James Brady

17.8k64455

2

I don't have python 2.6, but since that link contained the code for combinations, I was able to get it working. Thanks again!

– Ben
Jan 21 '09 at 11:38

Ah, yes - I didn't see that it was 2.6 only... updated my answer

– James Brady
Jan 21 '09 at 12:52

10

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

– silgon
Sep 14 '17 at 12:23

add a comment |

338

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!

edited Jan 21 '09 at 12:52

answered Jan 21 '09 at 11:20

James Brady

17.8k64455

2

I don't have python 2.6, but since that link contained the code for combinations, I was able to get it working. Thanks again!

– Ben
Jan 21 '09 at 11:38

Ah, yes - I didn't see that it was 2.6 only... updated my answer

– James Brady
Jan 21 '09 at 12:52

10

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

– silgon
Sep 14 '17 at 12:23

add a comment |

338

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!

edited Jan 21 '09 at 12:52

answered Jan 21 '09 at 11:20

James Brady

17.8k64455

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!

edited Jan 21 '09 at 12:52

answered Jan 21 '09 at 11:20

James Brady

17.8k64455

edited Jan 21 '09 at 12:52

answered Jan 21 '09 at 11:20

James Brady

17.8k64455

answered Jan 21 '09 at 11:20

James Brady

17.8k64455

answered Jan 21 '09 at 11:20

James Brady

17.8k64455

2

I don't have python 2.6, but since that link contained the code for combinations, I was able to get it working. Thanks again!

– Ben
Jan 21 '09 at 11:38

Ah, yes - I didn't see that it was 2.6 only... updated my answer

– James Brady
Jan 21 '09 at 12:52

10

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

– silgon
Sep 14 '17 at 12:23

add a comment |

2

I don't have python 2.6, but since that link contained the code for combinations, I was able to get it working. Thanks again!

– Ben
Jan 21 '09 at 11:38

Ah, yes - I didn't see that it was 2.6 only... updated my answer

– James Brady
Jan 21 '09 at 12:52

10

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

– silgon
Sep 14 '17 at 12:23

I don't have python 2.6, but since that link contained the code for combinations, I was able to get it working. Thanks again!

– Ben
Jan 21 '09 at 11:38

Ah, yes - I didn't see that it was 2.6 only... updated my answer

– James Brady
Jan 21 '09 at 12:52

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

– silgon
Sep 14 '17 at 12:23

add a comment |

536

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)

edited May 1 '18 at 21:01

Steven C. Howell

4,26633562

answered May 5 '11 at 12:56

Dan H

7,93032328

29

Thanks for the support! In the weeks since I've posted the above reply, I've found that the NAME of the concept for what Ben is looking for is the "powerset" of the original set of 15 items. In fact, an example implementation is given on the standard python "itertools" doc page: docs.python.org/library/itertools.html (grep for "powerset").

– Dan H
Nov 16 '11 at 17:45

Alabaster's answer -- which answer are you referring to? Maybe its better to leave that reference out and concentrate on the question an your answer :)

– Wolf
Jul 21 '16 at 9:12

1

@wolf: Apparently either "Alabaster's answer" has been deleted or the user changed his name some time in the five years since I posted my answer. (I think "Alabaster" is now "James Brady".) I don't think it is unusual or against guidelines to discuss the strengths or weaknesses of other answers in one's own answer; it helps readers compare and contrast, IMO.

– Dan H
Jul 26 '16 at 13:02

16

For anyone reading this far: The powerset() generator function in the recipes section of the itertools documentation is simpler, potentially uses less memory, and is likely faster than the implementation shown here.

– martineau
Oct 25 '16 at 17:16

2

@martineau: Maybe post that as an answer?

– naught101
Dec 5 '16 at 22:42

|
show 7 more comments

536

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)

edited May 1 '18 at 21:01

Steven C. Howell

4,26633562

answered May 5 '11 at 12:56

Dan H

7,93032328

29

Thanks for the support! In the weeks since I've posted the above reply, I've found that the NAME of the concept for what Ben is looking for is the "powerset" of the original set of 15 items. In fact, an example implementation is given on the standard python "itertools" doc page: docs.python.org/library/itertools.html (grep for "powerset").

– Dan H
Nov 16 '11 at 17:45

Alabaster's answer -- which answer are you referring to? Maybe its better to leave that reference out and concentrate on the question an your answer :)

– Wolf
Jul 21 '16 at 9:12

1

@wolf: Apparently either "Alabaster's answer" has been deleted or the user changed his name some time in the five years since I posted my answer. (I think "Alabaster" is now "James Brady".) I don't think it is unusual or against guidelines to discuss the strengths or weaknesses of other answers in one's own answer; it helps readers compare and contrast, IMO.

– Dan H
Jul 26 '16 at 13:02

16

For anyone reading this far: The powerset() generator function in the recipes section of the itertools documentation is simpler, potentially uses less memory, and is likely faster than the implementation shown here.

– martineau
Oct 25 '16 at 17:16

2

@martineau: Maybe post that as an answer?

– naught101
Dec 5 '16 at 22:42

|
show 7 more comments

536

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)

edited May 1 '18 at 21:01

Steven C. Howell

4,26633562

answered May 5 '11 at 12:56

Dan H

7,93032328

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)

edited May 1 '18 at 21:01

Steven C. Howell

4,26633562

answered May 5 '11 at 12:56

Dan H

7,93032328

edited May 1 '18 at 21:01

Steven C. Howell

4,26633562

edited May 1 '18 at 21:01

Steven C. Howell

4,26633562

edited May 1 '18 at 21:01

Steven C. Howell

4,26633562

answered May 5 '11 at 12:56

Dan H

7,93032328

answered May 5 '11 at 12:56

Dan H

7,93032328

answered May 5 '11 at 12:56

Dan H

7,93032328

29

Thanks for the support! In the weeks since I've posted the above reply, I've found that the NAME of the concept for what Ben is looking for is the "powerset" of the original set of 15 items. In fact, an example implementation is given on the standard python "itertools" doc page: docs.python.org/library/itertools.html (grep for "powerset").

– Dan H
Nov 16 '11 at 17:45

Alabaster's answer -- which answer are you referring to? Maybe its better to leave that reference out and concentrate on the question an your answer :)

– Wolf
Jul 21 '16 at 9:12

1

@wolf: Apparently either "Alabaster's answer" has been deleted or the user changed his name some time in the five years since I posted my answer. (I think "Alabaster" is now "James Brady".) I don't think it is unusual or against guidelines to discuss the strengths or weaknesses of other answers in one's own answer; it helps readers compare and contrast, IMO.

– Dan H
Jul 26 '16 at 13:02

16

For anyone reading this far: The powerset() generator function in the recipes section of the itertools documentation is simpler, potentially uses less memory, and is likely faster than the implementation shown here.

– martineau
Oct 25 '16 at 17:16

2

@martineau: Maybe post that as an answer?

– naught101
Dec 5 '16 at 22:42

|
show 7 more comments

29

Thanks for the support! In the weeks since I've posted the above reply, I've found that the NAME of the concept for what Ben is looking for is the "powerset" of the original set of 15 items. In fact, an example implementation is given on the standard python "itertools" doc page: docs.python.org/library/itertools.html (grep for "powerset").

– Dan H
Nov 16 '11 at 17:45

Alabaster's answer -- which answer are you referring to? Maybe its better to leave that reference out and concentrate on the question an your answer :)

– Wolf
Jul 21 '16 at 9:12

1

@wolf: Apparently either "Alabaster's answer" has been deleted or the user changed his name some time in the five years since I posted my answer. (I think "Alabaster" is now "James Brady".) I don't think it is unusual or against guidelines to discuss the strengths or weaknesses of other answers in one's own answer; it helps readers compare and contrast, IMO.

– Dan H
Jul 26 '16 at 13:02

16

For anyone reading this far: The powerset() generator function in the recipes section of the itertools documentation is simpler, potentially uses less memory, and is likely faster than the implementation shown here.

– martineau
Oct 25 '16 at 17:16

2

@martineau: Maybe post that as an answer?

– naught101
Dec 5 '16 at 22:42

Thanks for the support! In the weeks since I've posted the above reply, I've found that the NAME of the concept for what Ben is looking for is the "powerset" of the original set of 15 items. In fact, an example implementation is given on the standard python "itertools" doc page: docs.python.org/library/itertools.html (grep for "powerset").

– Dan H
Nov 16 '11 at 17:45

Alabaster's answer -- which answer are you referring to? Maybe its better to leave that reference out and concentrate on the question an your answer :)

– Wolf
Jul 21 '16 at 9:12

@wolf: Apparently either "Alabaster's answer" has been deleted or the user changed his name some time in the five years since I posted my answer. (I think "Alabaster" is now "James Brady".) I don't think it is unusual or against guidelines to discuss the strengths or weaknesses of other answers in one's own answer; it helps readers compare and contrast, IMO.

– Dan H
Jul 26 '16 at 13:02

For anyone reading this far: The powerset() generator function in the recipes section of the itertools documentation is simpler, potentially uses less memory, and is likely faster than the implementation shown here.

– martineau
Oct 25 '16 at 17:16

@martineau: Maybe post that as an answer?

– naught101
Dec 5 '16 at 22:42

|
show 7 more comments

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

edited Aug 11 '18 at 20:06

Greg

3,99111730

answered Jul 1 '11 at 0:21

ninjagecko

61.2k17113122

add a comment |

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

edited Aug 11 '18 at 20:06

Greg

3,99111730

answered Jul 1 '11 at 0:21

ninjagecko

61.2k17113122

add a comment |

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

edited Aug 11 '18 at 20:06

Greg

3,99111730

answered Jul 1 '11 at 0:21

ninjagecko

61.2k17113122

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

edited Aug 11 '18 at 20:06

Greg

3,99111730

answered Jul 1 '11 at 0:21

ninjagecko

61.2k17113122

edited Aug 11 '18 at 20:06

Greg

3,99111730

edited Aug 11 '18 at 20:06

Greg

3,99111730

edited Aug 11 '18 at 20:06

Greg

3,99111730

answered Jul 1 '11 at 0:21

ninjagecko

61.2k17113122

answered Jul 1 '11 at 0:21

ninjagecko

61.2k17113122

answered Jul 1 '11 at 0:21

ninjagecko

61.2k17113122

add a comment |

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)

edited Aug 1 '18 at 15:38

answered Dec 6 '16 at 1:45

martineau

69.3k1092186

add a comment |

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)

edited Aug 1 '18 at 15:38

answered Dec 6 '16 at 1:45

martineau

69.3k1092186

add a comment |

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)

edited Aug 1 '18 at 15:38

answered Dec 6 '16 at 1:45

martineau

69.3k1092186

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)

edited Aug 1 '18 at 15:38

answered Dec 6 '16 at 1:45

martineau

69.3k1092186

edited Aug 1 '18 at 15:38

answered Dec 6 '16 at 1:45

martineau

69.3k1092186

answered Dec 6 '16 at 1:45

martineau

69.3k1092186

answered Dec 6 '16 at 1:45

martineau

69.3k1092186

add a comment |

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

answered May 19 '14 at 17:25

darxtrix

1,06711524

Can this be modified to return a list of lists instead of printing?

– James Vickery
Nov 9 '17 at 2:14

@JamesVickery yes, you could look at either making a list outside of the function and appending to that, or (better) make the function a generator, have a look at the 'yield' keyword :)

– Dangercrow
Nov 12 '17 at 14:01

new_data = copy.copy(data) - this row is redundant as far as I see, it doesn't influence on anything

– Dmitriy Fialkovskiy
Oct 25 '18 at 14:27

add a comment |

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

answered May 19 '14 at 17:25

darxtrix

1,06711524

Can this be modified to return a list of lists instead of printing?

– James Vickery
Nov 9 '17 at 2:14

@JamesVickery yes, you could look at either making a list outside of the function and appending to that, or (better) make the function a generator, have a look at the 'yield' keyword :)

– Dangercrow
Nov 12 '17 at 14:01

new_data = copy.copy(data) - this row is redundant as far as I see, it doesn't influence on anything

– Dmitriy Fialkovskiy
Oct 25 '18 at 14:27

add a comment |

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

answered May 19 '14 at 17:25

darxtrix

1,06711524

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

answered May 19 '14 at 17:25

darxtrix

1,06711524

answered May 19 '14 at 17:25

darxtrix

1,06711524

answered May 19 '14 at 17:25

darxtrix

1,06711524

answered May 19 '14 at 17:25

darxtrix

1,06711524

Can this be modified to return a list of lists instead of printing?

– James Vickery
Nov 9 '17 at 2:14

@JamesVickery yes, you could look at either making a list outside of the function and appending to that, or (better) make the function a generator, have a look at the 'yield' keyword :)

– Dangercrow
Nov 12 '17 at 14:01

new_data = copy.copy(data) - this row is redundant as far as I see, it doesn't influence on anything

– Dmitriy Fialkovskiy
Oct 25 '18 at 14:27

add a comment |

Can this be modified to return a list of lists instead of printing?

– James Vickery
Nov 9 '17 at 2:14

@JamesVickery yes, you could look at either making a list outside of the function and appending to that, or (better) make the function a generator, have a look at the 'yield' keyword :)

– Dangercrow
Nov 12 '17 at 14:01

new_data = copy.copy(data) - this row is redundant as far as I see, it doesn't influence on anything

– Dmitriy Fialkovskiy
Oct 25 '18 at 14:27

Can this be modified to return a list of lists instead of printing?

– James Vickery
Nov 9 '17 at 2:14

@JamesVickery yes, you could look at either making a list outside of the function and appending to that, or (better) make the function a generator, have a look at the 'yield' keyword :)

– Dangercrow
Nov 12 '17 at 14:01

new_data = copy.copy(data) - this row is redundant as far as I see, it doesn't influence on anything

– Dmitriy Fialkovskiy
Oct 25 '18 at 14:27

add a comment |

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

edited Feb 7 at 8:13

answered Jun 25 '14 at 7:08

Mathieu Rodic

4,88523140

This is a permutation

– AdHominem
Oct 28 '16 at 19:44

11

@AdHominem: no, it's not. It's a list of all combinations. Permutations would include, e.g. ['b', 'a'].

– naught101
Dec 5 '16 at 22:44

TypeError: can only concatenate list (not "map") to list

– 0x48piraj
Feb 6 at 0:28

@0x48piraj: thank you for noticing, I edited my answer consequently!

– Mathieu Rodic
Feb 7 at 8:14

add a comment |

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

edited Feb 7 at 8:13

answered Jun 25 '14 at 7:08

Mathieu Rodic

4,88523140

This is a permutation

– AdHominem
Oct 28 '16 at 19:44

11

@AdHominem: no, it's not. It's a list of all combinations. Permutations would include, e.g. ['b', 'a'].

– naught101
Dec 5 '16 at 22:44

TypeError: can only concatenate list (not "map") to list

– 0x48piraj
Feb 6 at 0:28

@0x48piraj: thank you for noticing, I edited my answer consequently!

– Mathieu Rodic
Feb 7 at 8:14

add a comment |

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

edited Feb 7 at 8:13

answered Jun 25 '14 at 7:08

Mathieu Rodic

4,88523140

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

edited Feb 7 at 8:13

answered Jun 25 '14 at 7:08

Mathieu Rodic

4,88523140

edited Feb 7 at 8:13

answered Jun 25 '14 at 7:08

Mathieu Rodic

4,88523140

answered Jun 25 '14 at 7:08

Mathieu Rodic

4,88523140

answered Jun 25 '14 at 7:08

Mathieu Rodic

4,88523140

This is a permutation

– AdHominem
Oct 28 '16 at 19:44

11

@AdHominem: no, it's not. It's a list of all combinations. Permutations would include, e.g. ['b', 'a'].

– naught101
Dec 5 '16 at 22:44

TypeError: can only concatenate list (not "map") to list

– 0x48piraj
Feb 6 at 0:28

@0x48piraj: thank you for noticing, I edited my answer consequently!

– Mathieu Rodic
Feb 7 at 8:14

add a comment |

This is a permutation

– AdHominem
Oct 28 '16 at 19:44

11

@AdHominem: no, it's not. It's a list of all combinations. Permutations would include, e.g. ['b', 'a'].

– naught101
Dec 5 '16 at 22:44

TypeError: can only concatenate list (not "map") to list

– 0x48piraj
Feb 6 at 0:28

@0x48piraj: thank you for noticing, I edited my answer consequently!

– Mathieu Rodic
Feb 7 at 8:14

This is a permutation

– AdHominem
Oct 28 '16 at 19:44

@AdHominem: no, it's not. It's a list of all combinations. Permutations would include, e.g. ['b', 'a'].

– naught101
Dec 5 '16 at 22:44

TypeError: can only concatenate list (not "map") to list

– 0x48piraj
Feb 6 at 0:28

@0x48piraj: thank you for noticing, I edited my answer consequently!

– Mathieu Rodic
Feb 7 at 8:14

add a comment |

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

answered Aug 24 '11 at 10:24

HongboZhu

2,92422128

1

Nice example. I love generators... and I love Python for having them! This example only has one combinations() object around at a time, and yields one of the combinations at time. (Perhaps you want to add the def block around this -- as a usage example.) Note that my implementation (with chain(), given above) is not too much worse: it's true that is creates all len(iterable) generators at once... but it does NOT create all 2 ** len(iterable) combinations at once, as -- to my understanding -- chain "uses up" the first generator before drawing from subsequent ones.

– Dan H
Nov 16 '11 at 17:54

add a comment |

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

answered Aug 24 '11 at 10:24

HongboZhu

2,92422128

1

Nice example. I love generators... and I love Python for having them! This example only has one combinations() object around at a time, and yields one of the combinations at time. (Perhaps you want to add the def block around this -- as a usage example.) Note that my implementation (with chain(), given above) is not too much worse: it's true that is creates all len(iterable) generators at once... but it does NOT create all 2 ** len(iterable) combinations at once, as -- to my understanding -- chain "uses up" the first generator before drawing from subsequent ones.

– Dan H
Nov 16 '11 at 17:54

add a comment |

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

answered Aug 24 '11 at 10:24

HongboZhu

2,92422128

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

answered Aug 24 '11 at 10:24

HongboZhu

2,92422128

answered Aug 24 '11 at 10:24

HongboZhu

2,92422128

answered Aug 24 '11 at 10:24

HongboZhu

2,92422128

answered Aug 24 '11 at 10:24

HongboZhu

2,92422128

1

Nice example. I love generators... and I love Python for having them! This example only has one combinations() object around at a time, and yields one of the combinations at time. (Perhaps you want to add the def block around this -- as a usage example.) Note that my implementation (with chain(), given above) is not too much worse: it's true that is creates all len(iterable) generators at once... but it does NOT create all 2 ** len(iterable) combinations at once, as -- to my understanding -- chain "uses up" the first generator before drawing from subsequent ones.

– Dan H
Nov 16 '11 at 17:54

add a comment |

1

Nice example. I love generators... and I love Python for having them! This example only has one combinations() object around at a time, and yields one of the combinations at time. (Perhaps you want to add the def block around this -- as a usage example.) Note that my implementation (with chain(), given above) is not too much worse: it's true that is creates all len(iterable) generators at once... but it does NOT create all 2 ** len(iterable) combinations at once, as -- to my understanding -- chain "uses up" the first generator before drawing from subsequent ones.

– Dan H
Nov 16 '11 at 17:54

Nice example. I love generators... and I love Python for having them! This example only has one combinations() object around at a time, and yields one of the combinations at time. (Perhaps you want to add the def block around this -- as a usage example.) Note that my implementation (with chain(), given above) is not too much worse: it's true that is creates all len(iterable) generators at once... but it does NOT create all 2 ** len(iterable) combinations at once, as -- to my understanding -- chain "uses up" the first generator before drawing from subsequent ones.

– Dan H
Nov 16 '11 at 17:54

add a comment |

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

edited Sep 14 '15 at 0:02

ninjagecko

61.2k17113122

answered Mar 17 '15 at 5:52

saimadhu.polamuri

2,45311518

Bug in this code: does not return the empty set. Might mean xrange(0, ...) but haven't tested. edit: I went ahead and edited your answer to fix it.

– ninjagecko
Sep 14 '15 at 0:01

add a comment |

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

edited Sep 14 '15 at 0:02

ninjagecko

61.2k17113122

answered Mar 17 '15 at 5:52

saimadhu.polamuri

2,45311518

Bug in this code: does not return the empty set. Might mean xrange(0, ...) but haven't tested. edit: I went ahead and edited your answer to fix it.

– ninjagecko
Sep 14 '15 at 0:01

add a comment |

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

edited Sep 14 '15 at 0:02

ninjagecko

61.2k17113122

answered Mar 17 '15 at 5:52

saimadhu.polamuri

2,45311518

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

edited Sep 14 '15 at 0:02

ninjagecko

61.2k17113122

answered Mar 17 '15 at 5:52

saimadhu.polamuri

2,45311518

edited Sep 14 '15 at 0:02

ninjagecko

61.2k17113122

edited Sep 14 '15 at 0:02

ninjagecko

61.2k17113122

edited Sep 14 '15 at 0:02

ninjagecko

61.2k17113122

answered Mar 17 '15 at 5:52

saimadhu.polamuri

2,45311518

answered Mar 17 '15 at 5:52

saimadhu.polamuri

2,45311518

answered Mar 17 '15 at 5:52

saimadhu.polamuri

2,45311518

Bug in this code: does not return the empty set. Might mean xrange(0, ...) but haven't tested. edit: I went ahead and edited your answer to fix it.

– ninjagecko
Sep 14 '15 at 0:01

add a comment |

Bug in this code: does not return the empty set. Might mean xrange(0, ...) but haven't tested. edit: I went ahead and edited your answer to fix it.

– ninjagecko
Sep 14 '15 at 0:01

Bug in this code: does not return the empty set. Might mean xrange(0, ...) but haven't tested. edit: I went ahead and edited your answer to fix it.

– ninjagecko
Sep 14 '15 at 0:01

add a comment |

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

answered Dec 20 '16 at 4:29

LectureMaker

1,20511115

add a comment |

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

answered Dec 20 '16 at 4:29

LectureMaker

1,20511115

add a comment |

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

answered Dec 20 '16 at 4:29

LectureMaker

1,20511115

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

answered Dec 20 '16 at 4:29

LectureMaker

1,20511115

answered Dec 20 '16 at 4:29

LectureMaker

1,20511115

answered Dec 20 '16 at 4:29

LectureMaker

1,20511115

answered Dec 20 '16 at 4:29

LectureMaker

1,20511115

add a comment |

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 [c for i in range(len(x)+1) for c in combinations(x,i)]

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

answered Sep 14 '15 at 0:13

ninjagecko

61.2k17113122

add a comment |

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 [c for i in range(len(x)+1) for c in combinations(x,i)]

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

answered Sep 14 '15 at 0:13

ninjagecko

61.2k17113122

add a comment |

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 [c for i in range(len(x)+1) for c in combinations(x,i)]

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

answered Sep 14 '15 at 0:13

ninjagecko

61.2k17113122

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 [c for i in range(len(x)+1) for c in combinations(x,i)]

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

answered Sep 14 '15 at 0:13

ninjagecko

61.2k17113122

answered Sep 14 '15 at 0:13

ninjagecko

61.2k17113122

answered Sep 14 '15 at 0:13

ninjagecko

61.2k17113122

answered Sep 14 '15 at 0:13

ninjagecko

61.2k17113122

add a comment |

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

edited May 23 '17 at 12:10

Community♦

answered Sep 13 '15 at 23:28

ninjagecko

61.2k17113122

add a comment |

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

edited May 23 '17 at 12:10

Community♦

answered Sep 13 '15 at 23:28

ninjagecko

61.2k17113122

add a comment |

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

edited May 23 '17 at 12:10

Community♦

answered Sep 13 '15 at 23:28

ninjagecko

61.2k17113122

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

edited May 23 '17 at 12:10

Community♦

answered Sep 13 '15 at 23:28

ninjagecko

61.2k17113122

edited May 23 '17 at 12:10

Community♦

edited May 23 '17 at 12:10

Community♦

edited May 23 '17 at 12:10

Community♦

answered Sep 13 '15 at 23:28

ninjagecko

61.2k17113122

answered Sep 13 '15 at 23:28

ninjagecko

61.2k17113122

answered Sep 13 '15 at 23:28

ninjagecko

61.2k17113122

add a comment |

It could be done using itertools

For permutations

This method takes a list as an input and return an object list of tuples that contain permutation of length L in a list form.

# A Python program to print all  

# permutations of given length 

from itertools import permutations 



# Get all permutations of length 2 

# and length 2 

perm = permutations([1, 2, 3], 2) 



# Print the obtained permutations 

for i in list(perm): 

    print (i)

For Combination

This method takes a list and a input r as a input and return a object list of tuples which contain all possible combination of length r in a list form.

# A Python program to print all  

# combinations of given length 

from itertools import combinations 



# Get all combinations of [1, 2, 3] 

# and length 2 

comb = combinations([1, 2, 3], 2) 



# Print the obtained combinations 

for i in list(comb): 

    print (i)

see this

answered Sep 28 '18 at 13:30

Umer

753716

add a comment |

It could be done using itertools

For permutations

This method takes a list as an input and return an object list of tuples that contain permutation of length L in a list form.

# A Python program to print all  

# permutations of given length 

from itertools import permutations 



# Get all permutations of length 2 

# and length 2 

perm = permutations([1, 2, 3], 2) 



# Print the obtained permutations 

for i in list(perm): 

    print (i)

For Combination

This method takes a list and a input r as a input and return a object list of tuples which contain all possible combination of length r in a list form.

# A Python program to print all  

# combinations of given length 

from itertools import combinations 



# Get all combinations of [1, 2, 3] 

# and length 2 

comb = combinations([1, 2, 3], 2) 



# Print the obtained combinations 

for i in list(comb): 

    print (i)

see this

answered Sep 28 '18 at 13:30

Umer

753716

add a comment |

It could be done using itertools

For permutations

This method takes a list as an input and return an object list of tuples that contain permutation of length L in a list form.

# A Python program to print all  

# permutations of given length 

from itertools import permutations 



# Get all permutations of length 2 

# and length 2 

perm = permutations([1, 2, 3], 2) 



# Print the obtained permutations 

for i in list(perm): 

    print (i)

For Combination

This method takes a list and a input r as a input and return a object list of tuples which contain all possible combination of length r in a list form.

# A Python program to print all  

# combinations of given length 

from itertools import combinations 



# Get all combinations of [1, 2, 3] 

# and length 2 

comb = combinations([1, 2, 3], 2) 



# Print the obtained combinations 

for i in list(comb): 

    print (i)

see this

answered Sep 28 '18 at 13:30

Umer

753716

It could be done using itertools

For permutations

This method takes a list as an input and return an object list of tuples that contain permutation of length L in a list form.

# A Python program to print all  

# permutations of given length 

from itertools import permutations 



# Get all permutations of length 2 

# and length 2 

perm = permutations([1, 2, 3], 2) 



# Print the obtained permutations 

for i in list(perm): 

    print (i)

For Combination

This method takes a list and a input r as a input and return a object list of tuples which contain all possible combination of length r in a list form.

# A Python program to print all  

# combinations of given length 

from itertools import combinations 



# Get all combinations of [1, 2, 3] 

# and length 2 

comb = combinations([1, 2, 3], 2) 



# Print the obtained combinations 

for i in list(comb): 

    print (i)

see this

answered Sep 28 '18 at 13:30

Umer

753716

answered Sep 28 '18 at 13:30

Umer

753716

answered Sep 28 '18 at 13:30

Umer

753716

answered Sep 28 '18 at 13:30

Umer

753716

add a comment |

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

edited May 1 '15 at 13:34

Mattia Maestrini

25.9k146680

answered May 1 '15 at 5:07

TiPS

371

So what this code appears to do is return [listOfCombinations, listOfCombinationsGroupedBySize]. Unfortunately when run with the demo input it gives 63 elements rather than 64; it seems to be missing the empty set (in this case, the empty string "").

– ninjagecko
Sep 13 '15 at 23:58

add a comment |

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

edited May 1 '15 at 13:34

Mattia Maestrini

25.9k146680

answered May 1 '15 at 5:07

TiPS

371

So what this code appears to do is return [listOfCombinations, listOfCombinationsGroupedBySize]. Unfortunately when run with the demo input it gives 63 elements rather than 64; it seems to be missing the empty set (in this case, the empty string "").

– ninjagecko
Sep 13 '15 at 23:58

add a comment |

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

edited May 1 '15 at 13:34

Mattia Maestrini

25.9k146680

answered May 1 '15 at 5:07

TiPS

371

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

edited May 1 '15 at 13:34

Mattia Maestrini

25.9k146680

answered May 1 '15 at 5:07

TiPS

371

edited May 1 '15 at 13:34

Mattia Maestrini

25.9k146680

edited May 1 '15 at 13:34

Mattia Maestrini

25.9k146680

edited May 1 '15 at 13:34

Mattia Maestrini

25.9k146680

answered May 1 '15 at 5:07

TiPS

371

answered May 1 '15 at 5:07

TiPS

371

answered May 1 '15 at 5:07

TiPS

371

So what this code appears to do is return [listOfCombinations, listOfCombinationsGroupedBySize]. Unfortunately when run with the demo input it gives 63 elements rather than 64; it seems to be missing the empty set (in this case, the empty string "").

– ninjagecko
Sep 13 '15 at 23:58

add a comment |

So what this code appears to do is return [listOfCombinations, listOfCombinationsGroupedBySize]. Unfortunately when run with the demo input it gives 63 elements rather than 64; it seems to be missing the empty set (in this case, the empty string "").

– ninjagecko
Sep 13 '15 at 23:58

So what this code appears to do is return [listOfCombinations, listOfCombinationsGroupedBySize]. Unfortunately when run with the demo input it gives 63 elements rather than 64; it seems to be missing the empty set (in this case, the empty string "").

– ninjagecko
Sep 13 '15 at 23:58

add a comment |

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

edited Oct 7 '17 at 6:18

answered Oct 6 '17 at 16:08

Cynadyde

788

add a comment |

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

edited Oct 7 '17 at 6:18

answered Oct 6 '17 at 16:08

Cynadyde

788

add a comment |

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

edited Oct 7 '17 at 6:18

answered Oct 6 '17 at 16:08

Cynadyde

788

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

edited Oct 7 '17 at 6:18

answered Oct 6 '17 at 16:08

Cynadyde

788

edited Oct 7 '17 at 6:18

answered Oct 6 '17 at 16:08

Cynadyde

788

answered Oct 6 '17 at 16:08

Cynadyde

788

answered Oct 6 '17 at 16:08

Cynadyde

788

add a comment |

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

answered Oct 22 '17 at 0:57

Pradeep Vairamani

2,02422344

add a comment |

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

answered Oct 22 '17 at 0:57

Pradeep Vairamani

2,02422344

add a comment |

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

answered Oct 22 '17 at 0:57

Pradeep Vairamani

2,02422344

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

answered Oct 22 '17 at 0:57

Pradeep Vairamani

2,02422344

answered Oct 22 '17 at 0:57

Pradeep Vairamani

2,02422344

answered Oct 22 '17 at 0:57

Pradeep Vairamani

2,02422344

answered Oct 22 '17 at 0:57

Pradeep Vairamani

2,02422344

add a comment |

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

answered Dec 19 '17 at 16:23

Abhishek

1,10821434

add a comment |

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

answered Dec 19 '17 at 16:23

Abhishek

1,10821434

add a comment |

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

answered Dec 19 '17 at 16:23

Abhishek

1,10821434

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

answered Dec 19 '17 at 16:23

Abhishek

1,10821434

answered Dec 19 '17 at 16:23

Abhishek

1,10821434

answered Dec 19 '17 at 16:23

Abhishek

1,10821434

answered Dec 19 '17 at 16:23

Abhishek

1,10821434

add a comment |

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

answered Aug 21 '11 at 19:10

zmk

42866

3

This proposal is to do string mangling to build up sets?!?! Holy crow.... And: it is not returning the powerset, but rather, something like combinations_with_replacement(). (See docs.python.org/library/…)

– Dan H
Nov 16 '11 at 18:00

This indeed does the same as combination_with_replacement(), but at least on my box this runs slightly faster than itertools. What can I say, I like list comprehensions.

– zmk
Nov 24 '11 at 23:16

1

Thank you for the answer! What about create listCombined with reversed lists such as ['A', 'A'], ['A', 'B'], ['A', 'C'], ['B', 'A'], ['B', 'B'], ['B', 'C'], ['C', 'A'], ['C', 'B'] and ['C', 'C'] that include everything?

– Karyo
Mar 19 '15 at 10:55

add a comment |

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

answered Aug 21 '11 at 19:10

zmk

42866

3

This proposal is to do string mangling to build up sets?!?! Holy crow.... And: it is not returning the powerset, but rather, something like combinations_with_replacement(). (See docs.python.org/library/…)

– Dan H
Nov 16 '11 at 18:00

This indeed does the same as combination_with_replacement(), but at least on my box this runs slightly faster than itertools. What can I say, I like list comprehensions.

– zmk
Nov 24 '11 at 23:16

1

Thank you for the answer! What about create listCombined with reversed lists such as ['A', 'A'], ['A', 'B'], ['A', 'C'], ['B', 'A'], ['B', 'B'], ['B', 'C'], ['C', 'A'], ['C', 'B'] and ['C', 'C'] that include everything?

– Karyo
Mar 19 '15 at 10:55

add a comment |

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

answered Aug 21 '11 at 19:10

zmk

42866

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

answered Aug 21 '11 at 19:10

zmk

42866

answered Aug 21 '11 at 19:10

zmk

42866

answered Aug 21 '11 at 19:10

zmk

42866

answered Aug 21 '11 at 19:10

zmk

42866

3

This proposal is to do string mangling to build up sets?!?! Holy crow.... And: it is not returning the powerset, but rather, something like combinations_with_replacement(). (See docs.python.org/library/…)

– Dan H
Nov 16 '11 at 18:00

This indeed does the same as combination_with_replacement(), but at least on my box this runs slightly faster than itertools. What can I say, I like list comprehensions.

– zmk
Nov 24 '11 at 23:16

1

Thank you for the answer! What about create listCombined with reversed lists such as ['A', 'A'], ['A', 'B'], ['A', 'C'], ['B', 'A'], ['B', 'B'], ['B', 'C'], ['C', 'A'], ['C', 'B'] and ['C', 'C'] that include everything?

– Karyo
Mar 19 '15 at 10:55

add a comment |

3

This proposal is to do string mangling to build up sets?!?! Holy crow.... And: it is not returning the powerset, but rather, something like combinations_with_replacement(). (See docs.python.org/library/…)

– Dan H
Nov 16 '11 at 18:00

This indeed does the same as combination_with_replacement(), but at least on my box this runs slightly faster than itertools. What can I say, I like list comprehensions.

– zmk
Nov 24 '11 at 23:16

1

Thank you for the answer! What about create listCombined with reversed lists such as ['A', 'A'], ['A', 'B'], ['A', 'C'], ['B', 'A'], ['B', 'B'], ['B', 'C'], ['C', 'A'], ['C', 'B'] and ['C', 'C'] that include everything?

– Karyo
Mar 19 '15 at 10:55

This proposal is to do string mangling to build up sets?!?! Holy crow.... And: it is not returning the powerset, but rather, something like combinations_with_replacement(). (See docs.python.org/library/…)

– Dan H
Nov 16 '11 at 18:00

This indeed does the same as combination_with_replacement(), but at least on my box this runs slightly faster than itertools. What can I say, I like list comprehensions.

– zmk
Nov 24 '11 at 23:16

Thank you for the answer! What about create listCombined with reversed lists such as ['A', 'A'], ['A', 'B'], ['A', 'C'], ['B', 'A'], ['B', 'B'], ['B', 'C'], ['C', 'A'], ['C', 'B'] and ['C', 'C'] that include everything?

– Karyo
Mar 19 '15 at 10:55

add a comment |

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

answered Feb 5 '17 at 3:42

Andres Ulloa

311

What is your implementation solving better than the previous implementations posted here.

– user1767754
Jan 1 '18 at 22:47

add a comment |

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

answered Feb 5 '17 at 3:42

Andres Ulloa

311

What is your implementation solving better than the previous implementations posted here.

– user1767754
Jan 1 '18 at 22:47

add a comment |

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

answered Feb 5 '17 at 3:42

Andres Ulloa

311

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

answered Feb 5 '17 at 3:42

Andres Ulloa

311

answered Feb 5 '17 at 3:42

Andres Ulloa

311

answered Feb 5 '17 at 3:42

Andres Ulloa

311

answered Feb 5 '17 at 3:42

Andres Ulloa

311

What is your implementation solving better than the previous implementations posted here.

– user1767754
Jan 1 '18 at 22:47

add a comment |

What is your implementation solving better than the previous implementations posted here.

– user1767754
Jan 1 '18 at 22:47

What is your implementation solving better than the previous implementations posted here.

– user1767754
Jan 1 '18 at 22:47

add a comment |

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([c for c in combinations([1, 2, 3, 4], 3)])

# [[1, 2, 3], [1, 2, 4], [1, 3, 4], [2, 3, 4]]



# get a hold of prepend

prepend = [c for c in combinations(, -1)][0]

prepend.append(None)



print([c for c in combinations([1, 2, 3, 4], 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

edited Nov 6 '17 at 13:52

answered Nov 6 '17 at 9:01

Modar

113

add a comment |

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([c for c in combinations([1, 2, 3, 4], 3)])

# [[1, 2, 3], [1, 2, 4], [1, 3, 4], [2, 3, 4]]



# get a hold of prepend

prepend = [c for c in combinations(, -1)][0]

prepend.append(None)



print([c for c in combinations([1, 2, 3, 4], 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

edited Nov 6 '17 at 13:52

answered Nov 6 '17 at 9:01

Modar

113

add a comment |

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([c for c in combinations([1, 2, 3, 4], 3)])

# [[1, 2, 3], [1, 2, 4], [1, 3, 4], [2, 3, 4]]



# get a hold of prepend

prepend = [c for c in combinations(, -1)][0]

prepend.append(None)



print([c for c in combinations([1, 2, 3, 4], 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

edited Nov 6 '17 at 13:52

answered Nov 6 '17 at 9:01

Modar

113

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([c for c in combinations([1, 2, 3, 4], 3)])

# [[1, 2, 3], [1, 2, 4], [1, 3, 4], [2, 3, 4]]



# get a hold of prepend

prepend = [c for c in combinations(, -1)][0]

prepend.append(None)



print([c for c in combinations([1, 2, 3, 4], 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

edited Nov 6 '17 at 13:52

answered Nov 6 '17 at 9:01

Modar

113

edited Nov 6 '17 at 13:52

answered Nov 6 '17 at 9:01

Modar

113

answered Nov 6 '17 at 9:01

Modar

113

answered Nov 6 '17 at 9:01

Modar

113

add a comment |

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)

answered Dec 17 '17 at 18:04

Apurva Singh

1,8341427

add a comment |

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)

answered Dec 17 '17 at 18:04

Apurva Singh

1,8341427

add a comment |

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)

answered Dec 17 '17 at 18:04

Apurva Singh

1,8341427

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)

answered Dec 17 '17 at 18:04

Apurva Singh

1,8341427

answered Dec 17 '17 at 18:04

Apurva Singh

1,8341427

answered Dec 17 '17 at 18:04

Apurva Singh

1,8341427

answered Dec 17 '17 at 18:04

Apurva Singh

1,8341427

add a comment |

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

answered Oct 12 '18 at 12:59

Laurynas Tamulevičius

702316

add a comment |

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

answered Oct 12 '18 at 12:59

Laurynas Tamulevičius

702316

add a comment |

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

answered Oct 12 '18 at 12:59

Laurynas Tamulevičius

702316

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

answered Oct 12 '18 at 12:59

Laurynas Tamulevičius

702316

answered Oct 12 '18 at 12:59

Laurynas Tamulevičius

702316

answered Oct 12 '18 at 12:59

Laurynas Tamulevičius

702316

answered Oct 12 '18 at 12:59

Laurynas Tamulevičius

702316

add a comment |

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 += [c, c+[a[0]]]

    return cs



>>> combs([1,2,3,4,5])

[, [1], [2], [2, 1], [3], [3, 1], [3, 2], ..., [5, 4, 3, 2, 1]]

edited Feb 8 at 22:24

answered Feb 1 at 13:02

Jonathan R

1,182512

add a comment |

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 += [c, c+[a[0]]]

    return cs



>>> combs([1,2,3,4,5])

[, [1], [2], [2, 1], [3], [3, 1], [3, 2], ..., [5, 4, 3, 2, 1]]

edited Feb 8 at 22:24

answered Feb 1 at 13:02

Jonathan R

1,182512

add a comment |

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 += [c, c+[a[0]]]

    return cs



>>> combs([1,2,3,4,5])

[, [1], [2], [2, 1], [3], [3, 1], [3, 2], ..., [5, 4, 3, 2, 1]]

edited Feb 8 at 22:24

answered Feb 1 at 13:02

Jonathan R

1,182512

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 += [c, c+[a[0]]]

    return cs



>>> combs([1,2,3,4,5])

[, [1], [2], [2, 1], [3], [3, 1], [3, 2], ..., [5, 4, 3, 2, 1]]

edited Feb 8 at 22:24

answered Feb 1 at 13:02

Jonathan R

1,182512

edited Feb 8 at 22:24

answered Feb 1 at 13:02

Jonathan R

1,182512

answered Feb 1 at 13:02

Jonathan R

1,182512

answered Feb 1 at 13:02

Jonathan R

1,182512

add a comment |

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

answered May 7 '16 at 19:17

Anoop

874517

1

If I'm right, this is the exact code copied from python documentation [docs.python.org/3.6/library/itertools.html ]. If so, please do ref the source.

– GabrielChu
Dec 18 '17 at 9:33

interesting approach

– pelos
Nov 26 '18 at 22:47

add a comment |

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

answered May 7 '16 at 19:17

Anoop

874517

1

If I'm right, this is the exact code copied from python documentation [docs.python.org/3.6/library/itertools.html ]. If so, please do ref the source.

– GabrielChu
Dec 18 '17 at 9:33

interesting approach

– pelos
Nov 26 '18 at 22:47

add a comment |

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

answered May 7 '16 at 19:17

Anoop

874517

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

answered May 7 '16 at 19:17

Anoop

874517

answered May 7 '16 at 19:17

Anoop

874517

answered May 7 '16 at 19:17

Anoop

874517

answered May 7 '16 at 19:17

Anoop

874517

1

If I'm right, this is the exact code copied from python documentation [docs.python.org/3.6/library/itertools.html ]. If so, please do ref the source.

– GabrielChu
Dec 18 '17 at 9:33

interesting approach

– pelos
Nov 26 '18 at 22:47

add a comment |

1

If I'm right, this is the exact code copied from python documentation [docs.python.org/3.6/library/itertools.html ]. If so, please do ref the source.

– GabrielChu
Dec 18 '17 at 9:33

interesting approach

– pelos
Nov 26 '18 at 22:47

If I'm right, this is the exact code copied from python documentation [docs.python.org/3.6/library/itertools.html ]. If so, please do ref the source.

– GabrielChu
Dec 18 '17 at 9:33

interesting approach

– pelos
Nov 26 '18 at 22:47

add a comment |

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)

answered Dec 4 '17 at 6:54

Expat C

add a comment |

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)

answered Dec 4 '17 at 6:54

Expat C

add a comment |

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)

answered Dec 4 '17 at 6:54

Expat C

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)

answered Dec 4 '17 at 6:54

Expat C

answered Dec 4 '17 at 6:54

Expat C

answered Dec 4 '17 at 6:54

Expat C

answered Dec 4 '17 at 6:54

Expat C

add a comment |

protected by Jean-François Fabre♦ Mar 9 '18 at 12:35

This page is only for reference, If you need detailed information, please check here

Search This Blog

Ufyukyu