Listing all combinations of a list up to length n (Python)

Question

What would be an efficient algorithm to do the following: given a list, we have to output all combinations of elements up to a length n. Let's say x = ['a','b','c','d','e'] and n = 2. The output should be:

[['a'], ['b'], ['c'], ['d'], ['e'], ['a', 'b'], ['a', 'c'], ['a', 'd'], ['a', 'e'], ['b', 'c'], ['b', 'd'], ['b', 'e'], ['c', 'd'], ['c', 'e'], ['d', 'e']]

Answer 1

You could use itertools.combinations and iterate for increasing lengths:

from itertools import combinations

x = ['a','b','c','d','e']
c = []
n = 2

for i in range(n):
    c.extend(combinations(x, i + 1))

print(c)

or, using a list comprehension:

from itertools import combinations

x = ['a','b','c','d','e']
n = 2
c = [comb for i in range(n) for comb in combinations(x, i + 1)]
print(c)

Answer 2

Code:

x = ['a', 'b', 'c', 'd', 'e']
result = []

for length in range(1,3):
    result.extend(itertools.combinations(x, length))

print result

Output:

[('a',), ('b',), ('c',), ('d',), ('e',), ('a', 'b'), ('a', 'c'), ('a', 'd'), ('a', 'e'), ('b', 'c'), ('b', 'd'), ('b', 'e'), ('c', 'd'), ('c', 'e'), ('d', 'e')]

Documentation:

• itertools.combinations()

Answer 3

Use itertools.combnations:

>>> x = ['a','b','c','d','e']
>>> n = 2
>>> import itertools
>>> [list(comb) for i in range(1, n+1) for comb in itertools.combinations(x, i)]
[['a'], ['b'], ['c'], ['d'], ['e'],
 ['a', 'b'], ['a', 'c'], ['a', 'd'], ['a', 'e'],
 ['b', 'c'], ['b', 'd'], ['b', 'e'],
 ['c', 'd'], ['c', 'e'], ['d', 'e']]

Answer 4

Since you're looking for an algorithm and not a tool... this gives all possible unique combinations.

x = ['a','b','c','d','e']
n = 2

outList = []
for i in range(0,len(x)):
    outEleList = []
    outEleList.append(x[i])
    outList.append(outEleList)
    for c in range(i,len(x)):
        out = []
        out.append(x[i])
        out.append(x[c])
        outList.append(out)

print outList