python recursion list combinations without using generator

Question

I am learning python3. To think more about recursion, I want to implement a function comb(n, k) that returns a list consisting of all the combinations of kk elements out of a set {1,2,…,n}.

I think it's not wise to use the loop since the number of the nested loop depends on k. So I consider it with recursion. I try to write the function inspired by This question while I can't get the right answer.

def combinations(sub, data_set, index, still_needed):
    if still_needed == 0:
        return sub

    for i in range(index, len(data_set)):
        sub.append(data_set[i])
        still_needed = still_needed - 1
        return combinations(sub, data_set, index+1, still_needed)

def comb(n, k):
    data_set = list(range(1, n+1))
    print (combinations([], data_set, 0, k))

If I test Comb(6,3), I only get [1,2,3]. I want to get all combinations. What's the problem in my code? or something important missed? I just want to learn the recursion of python and it is not a homework, thanks.

The expecting result is below :

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

While the order is not important. And I will appreciate that if there is any pythonic way to solve this question eg. nested [expression for item in iterable](since I have tried it but failed).

Thanks again.

If iteration (loop) is not wise because then the number of iterations depends on k, then recursion *definitely* is not wise because whether it crashes or not depends on k. — stelioslogothetis, Jul 11 '17 at 12:14
Can you post the desired result for your example input `Comb(6,3)`? — Ma0, Jul 11 '17 at 12:14
You do get the first combination. If you need more you have to chose an implementation that either `yield`s or collects all combinations (not `return`s the first found combination). — MSeifert, Jul 11 '17 at 12:16

Eric Duminil · Accepted Answer · 2017-07-11T13:32:34.893

7

The problem in your function is that you have a return statement inside your for loop: it stops execution of the function during the first iteration.

Here's the basic structure you could use for recursion:

def combinations(n, k, min_n=0, accumulator=None):
    if accumulator is None:
        accumulator = []
    if k == 0:
        return [accumulator]
    else:
        return [l for x in range(min_n, n)
                for l in combinations(n, k - 1, x + 1, accumulator + [x + 1])]

print(combinations(6, 3))
# [[1, 2, 3], [1, 2, 4], [1, 2, 5], [1, 2, 6], [1, 3, 4], [1, 3, 5], [1, 3, 6], [1, 4, 5], [1, 4, 6], [1, 5, 6], [2, 3, 4], [2, 3, 5], [2, 3, 6], [2, 4, 5], [2, 4, 6], [2, 5, 6], [3, 4, 5], [3, 4, 6], [3, 5, 6], [4, 5, 6]]

To check if the result's correct, you can test it against itertools:

import itertools
print(list(itertools.combinations(range(1,7),3)))
# [(1, 2, 3), (1, 2, 4), (1, 2, 5), (1, 2, 6), (1, 3, 4), (1, 3, 5), (1, 3, 6), (1, 4, 5), (1, 4, 6), (1, 5, 6), (2, 3, 4), (2, 3, 5), (2, 3, 6), (2, 4, 5), (2, 4, 6), (2, 5, 6), (3, 4, 5), (3, 4, 6), (3, 5, 6), (4, 5, 6)]
print(
        list(itertools.combinations(range(1, 7), 3))
          ==
        [tuple(comb) for comb in combinations(6, 3)]
     )
# True

edited Jul 11 '17 at 13:32

answered Jul 11 '17 at 12:22

Eric Duminil

52,989
9
71
124

Best to use an accumulator list, passed through in function signature, rather than concatenating new lists n number of times. List concatenation is expensive. – danny Jul 11 '17 at 12:35
@danny: Interesting. What do you mean by accumulator list? – Eric Duminil Jul 11 '17 at 12:41
Meaning create a list once at first iteration to hold accumulated results from recursion. Append to it and pass that through the recursive calls. Result is one list gets appended to on each iteration rather than new lists being created by concatenation. Eg, `def combinations(n, k, min_n=0, accumulator=None)` and call `combinations(n, k -1, x+1, accumulator=accumulator)` after appending to it. – danny Jul 11 '17 at 12:48
@danny: Thanks, is it what you meant? I think it uses `n` times less concatenations now. – Eric Duminil Jul 11 '17 at 12:56
2

Yup. Slight change though, having mutable objects in function declarations is bad practice (the same object would be used in multiple calls of the function even across imports in different modules and would give bad results). And yes, itertools is a better option performance wise, the question is to do with recursion though and this is a common pattern :) Also keep in mind python's recursion limit (10k). – danny Jul 11 '17 at 13:29

python recursion list combinations without using generator

1 Answers1

Linked