Recursively find all combinations of list

Question

Problem statement

I want to get all possible combinations out of my list (including the empty list).

My code so far is:

def combination(l):
    result = []
    for item in range(len(l)):
        cut_list = l[:item] + l[item + 1:]
        if len(cut_list) > 1:
            combination(cut_list)
        elif len(cut_list) == 1:
            result += cut_list
    return result


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

My output is an empty List

[]

i want this Output:

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

I am pretty sure something with my return is not right.

Any help is extremely appreciated.

Your `return result` looks right, its just that you are not doing anything with it once returned. — quamrana, Dec 07 '20 at 11:45
To elaborate on @quamrana 's comment: the main obvious error is on the line with the recursive call `combination(cut_list)`. This line makes a recursive call; the recursive call performs calculations to find the combinations of `cut_list`; but the return value of the recursive call is discarded. Instead you should probably write something like `result += combination(cut_list)`. At least this should give you a result which is not just an empty list. The overall logic of the algorithm is not completely correct, though, so the result will still not be exactly what you want, but it's a start. — Stef, Dec 07 '20 at 13:53

score 3 · Accepted Answer · answered Dec 07 '20 at 12:25

A recurrence relation can be found this way: "A combination of list l either uses the last element of l, or it doesn't."

So we find recursively the combinations of sublist l[:-1] (the sublist containing all elements except the last one); and then we either add or don't add the last element.

Recursive version

This recursion needs a base case. The base case is: if the list is empty, then the only combination is the empty combination.

def combinations(l):
    if l:
      result = combinations(l[:-1])
      return result + [c + [l[-1]] for c in result]
    else:
      return [[]]

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

Iterative version

The recurrence relation is great, but there is no need for recursion; for-loops work very well to apply recurrence relations repeatedly.

def combinations(l):
  result = [[]]
  for x in l:
    result = result + [c + [x] for c in result]
  return result

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

Hello, Steff... Could we do the same function but to return only the combinations of N elements? For instance N = 2... Then what we expect to get is [1, 2], [1, 3], [2, 3] — lucasbbs, Aug 28 '21 at 03:06
@lucasbbs Sure we can. For the recursive version, it's as easy as adding an argument `n` with the number of desired elements (and being careful to update it correctly in the recursive calls). I would suggest that you ask a new questions (and link it here so I can come answer); but actually that question has already been asked and answered on stackoverflow. For instance: [How to get all combinations of length n](https://stackoverflow.com/questions/27974126/how-to-get-all-combinations-of-length-n-in-python) — Stef, Aug 28 '21 at 09:24

score 1 · Answer 2 · answered Dec 07 '20 at 11:50

1

Try this:

In [24]: import itertools

In [25]: l
Out[25]: [1, 2, 3]

In [26]: [sublist for item in [[list(x) for x in itertools.combinations(l,n)] for n in range(len(l)+1)] for sublist in item]
Out[26]: [[], [1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]]

answered Dec 07 '20 at 11:50

idar

614
6
13

This is the output iam looking for but my goal is to do it without itertools – FD GOD Dec 07 '20 at 11:55

Alain T. · Answer 3 · 2020-12-07T17:16:25.093

Here's how I would do it (as a generator):

def combinations(aList):
    yield []
    for i,v in enumerate(aList,1):
        yield from ([v]+c for c in combinations(aList[i:]))
    

for combo in combinations([1,2,3]): print(combo)

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

or as a list builder:

def combinations(aList):
    return [[]] + [ [v]+c for i,v in enumerate(aList,1) 
                          for c   in combinations(aList[i:]) ]

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

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

score 0 · Answer 4 · answered Dec 07 '20 at 11:53

this is what you wanted to do?

l = [3, 22, 10, 15, 32, 10, 5]


def f(ml: list):
    a = []
    for i1 in ml:
        for i2 in ml:
            if not i1 + i2 in a:
                a.append(i1 + i2)
    return a


print(f(l))

[6, 25, 13, 18, 35, 8, 44, 32, 37, 54, 27, 20, 42, 15, 30, 47, 64, 10]

milanbalazs · Answer 5 · 2020-12-07T12:29:18.723

You should pass your result list as well, like below. But I think this recursive function doesn't do that what you want to do.

def combination(l, result=[]):
    for item in range(len(l)):
        cut_list = l[:item] + l[item + 1:]
        if len(cut_list) > 1:
            combination(cut_list, result)
        elif len(cut_list) == 1:
            result += cut_list
    return result


print(combination([3, 22, 10, 15, 32, 10, 5]))

Result:

>>> python3 test.py 
[5, 10, 5, 32, 10, 32, 5, 10, 5, 15, 10, 15, 5, 32, 5, 15, 32, ...

You can get the all combinations/permutations without recursion:

Permutations:

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

Output:

>>> python3 test.py 
()
(1,)
(2,)
(3,)
(1, 2)
(1, 3)
(2, 1)
(2, 3)
(3, 1)
(3, 2)
(1, 2, 3)
(1, 3, 2)
(2, 1, 3)
(2, 3, 1)
(3, 1, 2)
(3, 2, 1)

Combinations (This mechanism matches with your description in your question):

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

Output:

>>> python3 test.py 
()
(1,)
(2,)
(3,)
(1, 2)
(1, 3)
(2, 3)
(1, 2, 3)

EDIT:

Of course, you can make a function from my below example and you can get the result as a nested list.

Code:

import itertools

def combination(l):
    result = []
    for L in range(0, len(l)+1):
        for subset in itertools.combinations(l, L):
            result.append(list(subset))
    return result

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

Output:

>>> python3 test.py 
[[], [1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]]

EDIT_2:

Solution without itertools module:

Code:

def combinations(return_len, iterable):
    if not return_len:
        return [[]]
    if not iterable:
        return []

    head = [iterable[0]]
    tail = iterable[1:]
    new_comb = [head + list_ for list_ in combinations(return_len - 1, tail)]

    return new_comb + combinations(return_len, tail)


input_list = [1, 2, 3]
result = []

for n in range(0, len(input_list) + 1):
    for single_result in combinations(n, input_list):
        result.append(single_result)

print(result)

Output:

>>> python3 test.py 
[[], [1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]]

I want an out smth like this [[], [1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]] with recursion and only one given parameter in my function — FD GOD, Dec 07 '20 at 12:02
I have edited my answer. Now the input/output format is the same as in your question! — milanbalazs, Dec 07 '20 at 12:11
Your first code doesn't work correctly, because of the mutable optional argument. Try calling the function twice and you'll get garbage results the second time. See also: [Python documentation / Gotchas / Mutable default arguments](https://docs.python-guide.org/writing/gotchas/#mutable-default-arguments) — Stef, Dec 07 '20 at 12:19
I am aware of usage a mutable option argument, I know it is extremely dangerous. I didn't say it is the best solution, I just wanted to show that the "original" recursive function in the question is not correct (Not only the `return` statement is faulty). But on the other hand, thanks for your remark. — milanbalazs, Dec 07 '20 at 12:22
@FD GOD, I have added a solution without `itertools` module. — milanbalazs, Dec 07 '20 at 12:29

Recursively find all combinations of list

5 Answers5

Recursive version

Iterative version

Linked