Get all possible (2^N) combinations of a list’s elements, of any length

Question

I have a list with 15 numbers. How can I produce all 32,768 combinations of those numbers (i.e., any number of elements, in the original order)?

I thought of looping through the decimal integers 1–32768 and using the binary representation of each numbers as a filter to pick out the appropriate list elements. Is there a better way to do it?

---

_{For combinations of a specific length, see Get all (n-choose-k) combinations of length n. Please use that question to close duplicates instead where appropriate.}

_{When closing questions about combinatorics as duplicates, it is very important to make sure of what OP actually wants, not the words that were used to describe the problem. It is extremely common for people who want, for example, a Cartesian product (see How to get the cartesian product of multiple lists) to ask about "combinations".}

Turpentine

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. – Readymix

@Readymix Using the Set library is not efficient as each are O(n) at the best. Thus adding n functions to a set is actually O(n^2)! – Plovdiv

From carefully reading the question, it seems that the OP is asking for the PowerSet of his list of 15 numbers, not all the combinations. I think this may be why the answers are all over the place. – Plovdiv

@Scott Biggs: are you sure you're taking about Python here? Set insertions and lookups are O(1) average case. They're like dictionaries. They use hashing. Python doesn't have a special set library (it's in the standard library). We're inserting numbers here not functions. (It would still be inefficient to use O(2^n) memory; the proper solution for people who want combinations rather than the powerset is a simple recursive implementation, or product, etc.) – Readymix

Answer 1

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!

Prot

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

is there anything that does not require r, i.e. combinations of any length subsequences of elements. – Begum

this is very good and pointed me to what really solved my problem, which was itertools.combination_with_replacement. – Foretell

the function writes intertools.combinations_with_replacement – Koren

Answer 2

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

Rakish

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"). – Rakish

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. – Timer

Is it possible to generate all the combinations in lexicographical order ? – Pitchblende

@guik: I'm 99% sure that itertools.combinations preserves the item order in the lists it yields. Thus, if the input is lexically sorted, then each of the outputs will be, as well. – Rakish

Yes, itertools.combinations generates the combinations of k among n in lexicographical order, but not all the combinations up to k among n. powerset generates all combinations up to k, but not in lexicographical order as far as I understand it: powerset([1,2]) --> [(), (1,), (2,), (1, 2)]. Shouldn't it be : [(), (1,), (1, 2), (2,)] ? – Pitchblende

@guik: I'm pretty sure some of the recursive solutions here do that. See, for example, the one by darxtrix. https://mcmap.net/q/63517/-get-all-possible-2-n-combinations-of-a-list-s-elements-of-any-length – Rakish

Is there an easy way to exclude the comma after single elements as in (1,)? – Introspect

@Introspect : that is just how Python prints tuples with one element. (The comma isn't "there" 'til you try to print it.) So you have options: 1: convert the item to a list first: print(list(item)) or 2: use ",".join(items) to avoid the one-element commas. – Rakish

just want to point out that a lot of the time it's better to be less snazzy and more readable. – Selfemployed

@Timer is there a way to use itertools.powerset() but limiting the minimum number of elements required to form a combination? For example I only want to consider combinations of length 2 and longer. – Piliferous

@Piliferous Just adapt the above using 2 as the lower bound in the range command... that is range(2, len(ss)+1)) – Rakish

Answer 3

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)

Timer

What is the list() conversion for in the first place? – Dreddy

@Alexander: To allow the iterable's length to be determined. – Timer

...but this is essentially a refactoring of Dan H's all_subsets code, just using chain.from_iterable(x) instead of chain(*x). – Flutterboard

Answer 4

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

Panther

Ah! Nice implementation.I recognize HEAD = a[0], TAIL = a[1:] from Prolog. Or car = a[0], cdr = a[1:] from Lisp. I wonder if we could use memoization here... – Correlate

True. List slicing is O(k) where k is the length of the slice. I guess one could speed this up by doing a lookup in a map which would make it O(1) in all runs but the first. Note though that this implementation should not be referenced for performance. For that better implementations exist. This implementation is only for simplicity and portability to most other languages. – Panther

community.schemewiki.org/?sicp-ex-2.32 This is a great answer to exercise 2.32 of the SICP book – Linger

Answer 5

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

Readymix

Answer 6

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

Esch

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

@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 :) – Vasculum

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

Answer 7

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

Cockeyed

This is a permutation – Magnuson

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

Answer 8

You can generate 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)]

Sorites

Cool. I was trying to build domain names from company names for the purposes of scraping the site and this helped to do this – Bedight

How does this add any information compared to prior answers using itertools.combinations? – Flutterboard

Answer 9

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

Dermatoid

Answer 10

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

Dwaynedweck

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. – Rakish

Answer 11

3 functions:

1. all combinations of n elements list
2. all combinations of n elements list where order is not distinct
3. all permutations

import sys

def permutations(a):
    return combinations(a, len(a))

def combinations(a, n):
    if n == 1:
        for x in a:
            yield [x]
    else:
        for i in range(len(a)):
            for x in combinations(a[:i] + a[i+1:], n-1):
                yield [a[i]] + x

def combinationsNoOrder(a, n):
    if n == 1:
        for x in a:
            yield [x]
    else:
        for i in range(len(a)):
            for x in combinationsNoOrder(a[:i], n-1):
                yield [a[i]] + x
    
if __name__ == "__main__":
    for s in combinations(list(map(int, sys.argv[2:])), int(sys.argv[1])):
        print(s)

Franklyn

I like this very much!!! Thank you!!! Python's combinatorics functions are a little bit strange though. In mathematics "combinations" function would be Variations, and "combinationsNoOrder" are actually combinations. I would guess that confuses people that come to python from the branch of mathematics, as it did to me this time. Anyway's, a nice solution, thanks a lot a gain! – Post

Answer 12

from itertools import combinations


features = ['A', 'B', 'C']
tmp = []
for i in range(len(features)):
    oc = combinations(features, i + 1)
    for c in oc:
        tmp.append(list(c))

---

output

[
 ['A'],
 ['B'],
 ['C'],
 ['A', 'B'],
 ['A', 'C'],
 ['B', 'C'],
 ['A', 'B', 'C']
]

Perni

Answer 13

You can also use the powerset function from the excellent more_itertools package.

from more_itertools import powerset

l = [1,2,3]
list(powerset(l))

# [(), (1,), (2,), (3,), (1, 2), (1, 3), (2, 3), (1, 2, 3)]

We can also verify, that it meets OP's requirement

from more_itertools import ilen

assert ilen(powerset(range(15))) == 32_768

Tertullian

Check the source code it's the same as @Timer answer, so probably you don't need to install the whole library for this tiny thing – Skelton

Answer 14

I like this problem because there are so many ways to implement it. I decided to create a reference answer for the future.

What to use in production?

The intertools' documentation has a self-contained example, why not use it in your code? Some people suggested using more_itertools.powerset, but it has exactly the same implementation! If I were you I wouldn't install the whole package for one tiny thing. Probably this is the best way to go:

import itertools

def powerset(iterable):
    "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
    s = list(iterable)
    return itertools.chain.from_iterable(combinations(s, r) for r in range(len(s)+1))

Other possible approaches

Approach 0: Using combinations

import itertools

def subsets(nums):
    result = []
    for i in range(len(nums) + 1):
        result += itertools.combinations(nums, i)
    return result

Approach 1: Straightforward recursion

def subsets(nums):
    result = []

    def powerset(alist, index, curr):
        if index == len(alist):
            result.append(curr)
            return

        powerset(alist, index + 1, curr + [alist[index]])
        powerset(alist, index + 1, curr)

    powerset(nums, 0, [])
    return result

Approach 2: Backtracking

def subsets(nums):
    result = []

    def backtrack(index, curr, k):
        if len(curr) == k:
            result.append(list(curr))
            return
        for i in range(index, len(nums)):
            curr.append(nums[i])
            backtrack(i + 1, curr, k)
            curr.pop()

    for k in range(len(nums) + 1):
        backtrack(0, [], k)
    return result

or

def subsets(nums):
    result = []

    def dfs(nums, index, path, result):
        result.append(path)
        for i in range(index, len(nums)):
            dfs(nums, i + 1, path + [nums[i]], result)

    dfs(nums, 0, [], result)
    return result

Approach 3: Bitmasking

def subsets(nums):
    res = []
    n = len(nums)
    for i in range(1 << n):
        aset = []
        for j in range(n):
            value = (1 << j) & i  # value = (i >> j) & 1
            if value:
                aset.append(nums[j])
        res.append(aset)
    return res

or (not really bitmasking, using intuition that there's exactly 2^n subsets)

def subsets(nums):
    subsets = []
    expected_subsets = 2 ** len(nums)

    def generate_subset(subset, nums):
        if len(subsets) >= expected_subsets:
            return
        if len(subsets) < expected_subsets:
            subsets.append(subset)
        for i in range(len(nums)):
            generate_subset(subset + [nums[i]], nums[i + 1:])

    generate_subset([], nums)
    return subsets

Approach 4: Cascading

def subsets(nums):
    result = [[]]
    for i in range(len(nums)):
        for j in range(len(result)):
            subset = list(result[j])
            subset.append(nums[i])
            result.append(subset)
    return result

Skelton

Nice overview! But what's chain in the first paragraph? Also curious how the different approaches compare performance wise? – Codycoe

@hans-bouwmeester I added missed import. Thanks for pointing that out! I hope I'll dedicate some time to check performance – Skelton

Answer 15

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

Readymix

Answer 16

Below is a "standard recursive answer", similar to the other similar answer https://mcmap.net/q/63517/-get-all-possible-2-n-combinations-of-a-list-s-elements-of-any-length . (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

Readymix

Answer 17

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

Choric

Answer 18

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)

Diabolism

Answer 19

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

Slavophile

Answer 20

I'm a bit late on this topic, but think I can help someone.

You can use product from itertools:

from itertools import product

n = [1, 2, 3]

result = product(n, repeat=3) # You can change the repeat more then n length

print(list(result))

Output:

[(1, 1, 1), (1, 1, 2), (1, 1, 3), (1, 2, 1), (1, 2, 2), (1, 2, 3), (1, 3, 1),
 (1, 3, 2), (1, 3, 3), (2, 1, 1), (2, 1, 2), (2, 1, 3), (2, 2, 1), (2, 2, 2),
 (2, 2, 3), (2, 3, 1), (2, 3, 2), (2, 3, 3), (3, 1, 1), (3, 1, 2), (3, 1, 3), 
(3, 2, 1), (3, 2, 2), (3, 2, 3), (3, 3, 1), (3, 3, 2), (3, 3, 3)]

Another example, but changing repeat arguement:

from itertools import product

n = [1, 2, 3]

result = product(n, repeat=4) # Changing repeat to 4
print(list(result))

Output:

(1, 1, 2, 3), (1, 1, 3, 1), (1, 1, 3, 2), (1, 1, 3, 3), (1, 2, 1, 1), 
(1, 2, 1, 2), (1, 2, 1, 3), (1, 2, 2, 1), (1, 2, 2, 2), (1, 2, 2, 3), 
(1, 2, 3, 1), (1, 2, 3, 2), (1, 2, 3, 3), (1, 3, 1, 1), (1, 3, 1, 2), 
(1, 3, 1, 3), (1, 3, 2, 1), (1, 3, 2, 2), (1, 3, 2, 3), (1, 3, 3, 1), 
(1, 3, 3, 2), (1, 3, 3, 3), (2, 1, 1, 1), (2, 1, 1, 2), (2, 1, 1, 3), 
(2, 1, 2, 1), (2, 1, 2, 2), (2, 1, 2, 3), (2, 1, 3, 1), (2, 1, 3, 2),
 (2, 1, 3, 3), (2, 2, 1, 1), (2, 2, 1, 2), (2, 2, 1, 3), (2, 2, 2, 1), 
(2, 2, 2, 2), (2, 2, 2, 3), (2, 2, 3, 1), (2, 2, 3, 2), (2, 2, 3, 3), 
(2, 3, 1, 1), (2, 3, 1, 2), (2, 3, 1, 3), (2, 3, 2, 1), (2, 3, 2, 2), 
(2, 3, 2, 3), (2, 3, 3, 1), (2, 3, 3, 2), (2, 3, 3, 3), (3, 1, 1, 1), 
(3, 1, 1, 2), (3, 1, 1, 3), (3, 1, 2, 1), (3, 1, 2, 2), (3, 1, 2, 3), 
(3, 1, 3, 1), (3, 1, 3, 2), (3, 1, 3, 3), (3, 2, 1, 1), (3, 2, 1, 2), 
(3, 2, 1, 3), (3, 2, 2, 1), (3, 2, 2, 2), (3, 2, 2, 3), (3, 2, 3, 1), 
(3, 2, 3, 2), (3, 2, 3, 3), (3, 3, 1, 1), (3, 3, 1, 2), (3, 3, 1, 3), 
(3, 3, 2, 1), (3, 3, 2, 2), (3, 3, 2, 3), (3, 3, 3, 1), (3, 3, 3, 2), 
(3, 3, 3, 3)]```

Curitiba

Answer 21

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

Martlet

Answer 22

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

Found

Answer 23

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

Cheroot

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 ""). – Readymix

Answer 24

As stated in the documentation

def combinations(iterable, r):
    # combinations('ABCD', 2) --> AB AC AD BC BD CD
    # combinations(range(4), 3) --> 012 013 023 123
    pool = tuple(iterable)
    n = len(pool)
    if r > n:
        return
    indices = list(range(r))
    yield tuple(pool[i] for i in indices)
    while True:
        for i in reversed(range(r)):
            if indices[i] != i + n - r:
                break
        else:
            return
        indices[i] += 1
        for j in range(i+1, r):
            indices[j] = indices[j-1] + 1
        yield tuple(pool[i] for i in indices)


x = [2, 3, 4, 5, 1, 6, 4, 7, 8, 3, 9]
for i in combinations(x, 2):
    print i

Napoleonnapoleonic

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. – Busywork

@Busywork just fixed it. The format wasn't also correct. – Symer

Answer 25

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

Lights

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

Answer 26

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

Alike

Answer 27

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)

Rioux

Answer 28

flag = 0
requiredCals =12
from itertools import chain, combinations

def powerset(iterable):
    s = list(iterable)  # allows duplicate elements
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))

stuff = [2,9,5,1,6]
for i, combo in enumerate(powerset(stuff), 1):
    if(len(combo)>0):
        #print(combo , sum(combo))
        if(sum(combo)== requiredCals):
            flag = 1
            break
if(flag==1):
    print('True')
else:
    print('else')

Backcross

Answer 29

I'm late to the party but would like to share the solution I found to the same issue: Specifically, I was looking to do sequential combinations, so for "STAR" I wanted "STAR", "TA", "AR", but not "SR".

lst = [S, T, A, R]
lstCombos = []
for Length in range(0,len(lst)+1):
    for i in lst:
        lstCombos.append(lst[lst.index(i):lst.index(i)+Length])

Duplicates can be filtered with adding in an additional if before the last line:

lst = [S, T, A, R]
lstCombos = []
for Length in range(0,len(lst)+1):
    for i in lst:
         if not lst[lst.index(i):lst.index(i)+Length]) in lstCombos:
             lstCombos.append(lst[lst.index(i):lst.index(i)+Length])

If for some reason this returns blank lists in the output, which happened to me, I added:

for subList in lstCombos:
    if subList = '':
         lstCombos.remove(subList)

Jacquelynejacquelynn

Answer 30

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

Triciatrick

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/…) – Rakish

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. – Triciatrick

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? – Hathor

Very interesting, but my python isn't quite up to understanding the subtleties here. Is there something special about using listCombined in different scopes and the fact that the for loop is all in one line? I'm trying to port this to Java with little luck. – Plovdiv

Answer 31

If you do not want to use combinations library, here is the solution:

nums = [1,2,3]
p = [[]]
fnl = [[],nums]

for i in range(len(nums)):
    for j in range(i+1,len(nums)):
        p[-1].append([i,j])

for i in range(len(nums)-3):
    p.append([])
    for m in p[-2]:
        p[-1].append(m+[m[-1]+1])

for i in p:
    for j in i:
        n = []
        for m in j:
            if m < len(nums):
                n.append(nums[m])
        if n not in fnl:
            fnl.append(n)

for i in nums:
    if [i] not in fnl:
        fnl.append([i])

print(fnl)

Output:

[[], [1, 2, 3], [1, 2], [1, 3], [2, 3], [1], [2], [3]]

Premundane

Answer 32

As mentioned by James Brady, you itertools.combinations is a key. But it is not a full solution.

Solution 1

import itertools
def all(lst):
    # ci is a bitmask which denotes particular combination,
    # see explanation below
    for ci in range(1, 2**len(lst)):
        yield tuple(itertools.compress(
            lst,
            [ci & (1<<k) for k in  range(0, len(lst))]
        ))

Solution 2

import itertools
def all_combs(lst):
    for r in range(1, len(lst)+1):
        for comb in itertools.combinations(lst, r):
            yield comb

Example

>>> list(all_combs([1,2,3]))
[(1,), (2,), (3,), (1, 2), (1, 3), (2, 3), (1, 2, 3)]
>>> len(list(all_combs([1,2,3])))
7
>>> len(list(all_combs(range(0, 15))))
32767
>>> list(all([1,2,3]))
[(1,), (2,), (1, 2), (3,), (1, 3), (2, 3), (1, 2, 3)]
>>> len(list(all(range(15))))
32767

Explanation

Assume your array A has length N. Let a bitmask B of length N will denote a particular combination C. If B[i] is 1, then A[i] belongs to combination C.

Solution 1 explanation

So we can just go over all bitmasks and filter source array A with this bitmask, which might be done by itertools.compress.

Solution 2 explanation

...Or, we can represent it as combinations

Now we need to consider cases, when there is single one in B, then when only two ones, and so on. Each case belongs to particular Combination. Thus once we combine all combinations sets we will get all subsequences.

Also, it becomes obvious that amount of all possible combinations in such case is 2^N - 1. We drop case when all B[i] are zeroes, since we assume empty set is not a combination. Otherwise, just don't substract 1.

Palazzo

Answer 33

I worked this one out from first principles. I am programming trading systems and needed a way of optimising the choice of assets for a basket of assets to be used in a system.

Code

The universe of assets is a tuple

ASSETS=('EURUSD', 'GBPUSD', 'USDCHF', 'USDJPY', 'USDCAD', 'AUDUSD', 'AUDNZD', 'AUDCAD', 'AUDCHF', 'AUDJPY', 'CHFJPY', 'EURGBP', 'EURAUD', 'EURCHF', 'EURJPY', 'EURNZD', 'EURCAD', 'GBPCHF', 'GBPJPY', 'CADCHF', 'CADJPY', 'GBPAUD', 'GBPCAD', 'GBPNZD', 'NZDCAD', 'NZDCHF', 'NZDJPY', 'NZDUSD', 'XAUUSD')
MAX_ASSETS = int('1'*len(ASSETS),2) # binary representation of all items selected ('11111111111111111111111111111' in this case) cast to an integer 536870911

Looping through all possible combinations:

for x in range (1,MAX_ASSETS+1):
  binx=bin(x)[2:].rjust(len(ASSETS),'0')
  print([asset for index, asset in enumerate(ASSETS) if int(binx[index])])# use list comprehension to obtain the list of assets selected according to the binary mask

In the first line of the above block we do not need to test the empty list so start the range at 1, and we do need the total universe of items therefore the upper limit of the range is extended by 1

In the second line we obtain the binary mask equivalent of x, stripped of the initial binary identifier, padded to the length of the tuple of assets

Finally we combine enumerating the ASSETS list to obtain both the value and the index, enabling us to evaluate the relevant member, identified by index, of the binary mask binx, with list comprehension to select the ASSETS where the corresponding member of binx is 1 or True

Use

During optimisation, it is now possible to treat ASSETS like any other parameter where the optimisation function takes a dictionary of parameters with tuples of start,finish and step eg

def optimiser(params)
  ...

params = {ASSET_LIST:(0,len(ASSETS),1),param_a:(start,finish,step),...}

optimiser(params)

within optimiser, the code below will be called, looping through vallues of ASSET_LIST as x

binx=bin(x)[2:].rjust(len(ASSETS),'0')
SELECTED_ASSETS = [asset for index, asset in enumerate(ASSETS) if int(binx[index])]

enabling SELECTED_ASSETS to be passed to the trade program as the asset basket to trade in that iteration of the optimiser.

I have found this to be much faster than using itertools especially as the length of ASSETS increases.

Does anyone have a faster solution?

Discussion