CODEWITHSUNDEEP
pythonlisttree
user75453
user75453

Reputation: 73

Find all k combination length of n elements

Hey im trying to find all k combination length of n elements with recursion without using any module

For example n = 4 so [0,1,2,3] and k=3 so the all the combination length 3 are 

>>>[0,0,0],[0,0,1],[0,0,2],[0,0,3],[0,0,4],[0,1,0],[0,1,1],[0,1,2]....

I tried to think on that like a tree but i didn't mange to go from here [0,0,4] for example to here [0,1,0] all i got was [0,0,0],[0,0,1],[0,0,2],[0,0,3],[0,0,4]

Upvotes: 0

Views: 68

Answers (2)

Andrea Pollini
Andrea Pollini

Reputation: 290

You can use itertools.combinations

import itertools
itertools.combinations('ABCD', 2)

Upvotes: 0

Jake Tae
Jake Tae

Reputation: 1741

We can achieve the bare minimum by using simple recursion. 

def combination(n, k):
    if not k:
        return [[]]
    res = []
    nums = list(range(n + 1))
    for comb in combination(n, k - 1):
        for num in nums:
            comb_copy = comb.copy()
            comb_copy.append(num)
            res.append(comb_copy)
    return res

Let's take a look at how this code works. First, as with any recursion problem, we establish the base case, which is when k == 0. In this case, we would return an empty nested list.

If k != 0, then we need to perform recursion. The gist of this problem is that we need to append some numbers to the result returned by combination(n, k - 1). For example, let's say we want to obtain the result for combination(2, 2). The result returned by combination(2, 1) would be

>>> combination(2, 1)
[[0], [1], [2]]

Given this information, how can we get combination(2, 2)? For some intuition, here is the result we want:

>>> combination(2, 2)
[[0, 0], [0, 1], [0, 2], [1, 0], [1, 1], [1, 2], [2, 0], [2, 1], [2, 2]]

Observe that all we need to do is to append the values 0, 1, and 2 to each element of combination(3, 1). In other words, take the first element, [0]. We append 0, 1, and 2 to this list, which results in [0, 0], [0, 1], [0, 2]. These are the first three elements of combination(3, 2).

Back to the code, we first call combination(n, k - 1), and append num to each list in the nested list returned by that function call. Finally, when the appending is over, we return res.

One fine detail here is that we create a copy of the list instead of appending to it directly. We do this in order to prevent modifying the original comb.

Here is the function in action with n = 4, k = 3:

>>> combination(4, 3)
[[0, 0, 0], [0, 0, 1], [0, 0, 2], [0, 0, 3], [0, 0, 4], [0, 1, 0], [0, 1, 1], [0, 1, 2], [0, 1, 3], [0, 1, 4], [0, 2, 0], [0, 2, 1], [0, 2, 2], [0, 2, 3], [0, 2, 4], [0, 3, 0], [0, 3, 1], [0, 3, 2], [0, 3, 3], [0, 3, 4], [0, 4, 0], [0, 4, 1], [0, 4, 2], [0, 4, 3], [0, 4, 4], [1, 0, 0], [1, 0, 1], [1, 0, 2], [1, 0, 3], [1, 0, 4], [1, 1, 0], [1, 1, 1], [1, 1, 2], [1, 1, 3], [1, 1, 4], [1, 2, 0], [1, 2, 1], [1, 2, 2], [1, 2, 3], [1, 2, 4], [1, 3, 0], [1, 3, 1], [1, 3, 2], [1, 3, 3], [1, 3, 4], [1, 4, 0], [1, 4, 1], [1, 4, 2], [1, 4, 3], [1, 4, 4], [2, 0, 0], [2, 0, 1], [2, 0, 2], [2, 0, 3], [2, 0, 4], [2, 1, 0], [2, 1, 1], [2, 1, 2], [2, 1, 3], [2, 1, 4], [2, 2, 0], [2, 2, 1], [2, 2, 2], [2, 2, 3], [2, 2, 4], [2, 3, 0], [2, 3, 1], [2, 3, 2], [2, 3, 3], [2, 3, 4], [2, 4, 0], [2, 4, 1], [2, 4, 2], [2, 4, 3], [2, 4, 4], [3, 0, 0], [3, 0, 1], [3, 0, 2], [3, 0, 3], [3, 0, 4], [3, 1, 0], [3, 1, 1], [3, 1, 2], [3, 1, 3], [3, 1, 4], [3, 2, 0], [3, 2, 1], [3, 2, 2], [3, 2, 3], [3, 2, 4], [3, 3, 0], [3, 3, 1], [3, 3, 2], [3, 3, 3], [3, 3, 4], [3, 4, 0], [3, 4, 1], [3, 4, 2], [3, 4, 3], [3, 4, 4], [4, 0, 0], [4, 0, 1], [4, 0, 2], [4, 0, 3], [4, 0, 4], [4, 1, 0], [4, 1, 1], [4, 1, 2], [4, 1, 3], [4, 1, 4], [4, 2, 0], [4, 2, 1], [4, 2, 2], [4, 2, 3], [4, 2, 4], [4, 3, 0], [4, 3, 1], [4, 3, 2], [4, 3, 3], [4, 3, 4], [4, 4, 0], [4, 4, 1], [4, 4, 2], [4, 4, 3], [4, 4, 4]]

Note that we can get fancier here by implementing things like dynamic programming, but is an optimization detail you might want to consider later.

Upvotes: 1

Related Questions