Python - Finding out all r combinations from a set of cardinality n

Question

I am trying to generate all possible 3 combinations from the set {1,2,3,4,5} using recursion.

Expected output: [[1,2,3],[1,2,4],[1,2,5],[2,3,4],[2,3,5],[3,4,5],[1,3,4],[1,3,5],[1,4,5],[2,4,5]]

The logic that I am using is that any 3-set combination will either have the first element in it or not have. I am also using the concatenation of lists. Example:

[[1,2,3]] + [[a,b]] gives [[1,2,3],[a,b]]

The below code that uses the above logic doesn't seem to work. I am self-learning so, if I make a mistake, please be patient with me. I am aware there are errors in my recursion. But, trying to backtrack the output in recursion problems is proving quite difficult for me. Could you please let me know where could be the flaw in this program and guide me towards suitable resources where such types of questions can be better handled. What is the right way of thinking in such questions? Thanks a lot for helping.

Code:

sol = [1,2,3,4,5]
b=3

y= []
def combinations(sol, b):
    global y
    if len(sol) == b or len(sol)==1 :
        return [sol]
    y.append([[sol[0]] + combinations(sol[1:], b-1)] +  combinations(sol[1:],b))
    return y

print(combinations(sol,b)

`y` holds your entire list of combinations, growing during each call.. You don't want `combinations` to return `y`. Think of what that does in the `y.append` call. Also, you don't need `global y`; you aren't assigning a new object to `y`. — Tim Roberts, Dec 01 '21 at 06:19
You can't really use recursion to create the set of all combinations, although you might use it to generate the individual combos. Remember that you need a loop; your first call is going to generate [1] plus the rest of the list, and [2] plus the rest of the list, and [3] plus the rest of the list. You're not doing that. — Tim Roberts, Dec 01 '21 at 06:23

score 2 · Answer 1 · answered Dec 01 '21 at 06:19

2

Use the machinery provided in itertools:

from itertools import combinations

list(combinations(v, 3))

OUTPUT

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

answered Dec 01 '21 at 06:19

nikeros

3,302
2
10
26

score 1 · Accepted Answer · answered Dec 01 '21 at 06:31

You CAN do this, by having your function be a generator. At each step, you loop through the possible starting cells, then loop through the results returned by the next step in the recursion.

sol = [1,2,3,4,5]
b=3

def combinations(sol, b):
    if b == 0:
        yield []
    else:
        for i in range(len(sol)-b+1):
            for j in combinations(sol[i+1:],b-1):
                yield [sol[i]]+j

print(list(combinations(sol,b)))

Output:

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

Python - Finding out all r combinations from a set of cardinality n

2 Answers2