CODEWITHSUNDEEP
pythonrecursionreturn
Kavan Patel
Kavan Patel

Reputation: 59

Store output of a recursive function

I wrote a recursive function to get all the possible combinations of a given list. Below is the code.

It takes a list argument and prints all possible combinations.

def getCombinations(a):
    a2 = []
    ans = ['' for i in range(len(a))]
    helper(a,ans,0)

def helper(a,ans,i):
    if i == len(ans):
        print (ans)
    else:
        ans[i] = ''
        helper(a,ans,i+1)
        ans[i] = a[i]
        helper(a,ans,i+1)

So If we call getCombinations([1,2,3]), it prints as below:

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

My question is how do I store the above result in a list. I have tried to look for solution, and I know the issue is function doesn't technically return anything, but even if I try replacing return with print(...) it doesn't work as expected and returns nothing.

Upvotes: 3

Views: 2069

Answers (2)

blhsing
blhsing

Reputation: 106445

You can use a function that extracts the first item from the given list and concatenate it with each of the combinations returned by a recursive call with the rest of the list, until the list becomes empty:

def getCombinations(lst):
    if lst:
        first, *rest = lst
        for value in '', first:
            for combination in getCombinations(rest):
                yield [value, *combination]
    else:
        yield []

so that list(getCombinations([1, 2, 3])) returns:

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

Upvotes: 0

Grismar
Grismar

Reputation: 31319

There's many ways to do this, but starting from your code, it's probably easiest to turn your function into a generator.

A generator doesn't return the whole result in one go, but each element as it becomes available. That way, you can replace your print with a yield and collect everything in a single list by wrapping the call to helper(a,ans,0) in a list().

However, since your code modifies the existing answer, you need to collect copies of the list, not the list itself, since that will change in later iterations.

So:

from copy import copy

def getCombinations(a):
    ans = ['' for i in range(len(a))]
    return list(helper(a,ans,0))

def helper(a,ans,i):
    if i == len(ans):
        yield copy(ans)
    else:
        ans[i] = ''
        yield from helper(a,ans,i+1)
        ans[i] = a[i]
        yield from helper(a,ans,i+1)

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

It's a very complicated way to do this though and very messy with the empty strings - why not use the standard libraries:

from itertools import combinations
print([c for n in range(4) for c in combinations([1, 2, 3], n)])

Or, more generically, for any list:

from itertools import combinations
def all_combinations(a):
    return([c for n in range(len(a)+1) for c in combinations(a, n)])
print(all_combinations([1, 2, 3]))

Upvotes: 2

Related Questions