K-combination recursive algorithm implementation

Question

Tried to implement this solution for finding n choose k. I have used recursion and this is how it goes for k as 4 and n as 6. Zero based

The idea is to have array of size k keeping sequence of indices of elements from the input array (which are numbers from 0 to n - 1) in increasing order. On each step, algorithm looks for the closest to the end item which can be incremented, increments it and fills up items right to that item.

 def get_combinations(str_index, k, n, index, limit, increment):
     if increment < limit:
         str_index[index] = increment
         result.add(tuple(str_index[0:index]+[increment]+str_index[index+1:]))
         get_combinations(str_index[:], k, n, index, limit, increment+1)
         if index >= 0 and str_index[index-1]+1 < increment:
             get_combinations(str_index[:], k, n, index-1, increment, str_index[index-1])

 result = set()
 word = "happyco"
 k = 4
 n = len(word)
 str_index = [i for i in range(k)]
 result.add(tuple(str_index))
 get_combinations(str_index, k, n, k-1, n, k)
 for combination in result:
     print("".join([word[i] for i in combination]))

However, there are some problems with this recursive approach:

a. It will cause stack overflow if n and k is huge.

b. I am using set to fix duplicates in the result.

Answer 1

1. There're a few more problems with code: for instance, it crashes for k = 0 (which is a valid input).

2. You implementation is really hard to follow: it's not clear what the arguments index, limit and increment stand for. They're way too generic. index: What kind of index? Sure, it's a position in the original string or list. But what does it represent? It's not an arbitrary position, is it? It's the index of the element that should be changed, isn't it? Why not call it idx_to_change, pos_to_change or something like that? The same goes for limit: what kind of limit is it?

3. There's too much stuff going on in the get_combinations function (like choosing the next position, generating a new combination and so on). I suggest splitting into a few smaller function with meaningful names.

4. I didn't fully understand your code, but if you need to keep a set to avoid duplicated, you're doing it wrong. I don't see why you need to recursion here either.

5. Let's go back to the algorithm:

   comb = [0..k-1]
   do 
       result.append(comb)
       // I assume that it returns null if there's no next combination
       comb = get_next_combination(comb)
   while comb != null
   

   Pretty simple, isn't it? Now we need to learn to generate the next combination. This part is already described in your post. So let's just create another function that does it.

Here's the code that implements this idea directly:

def get_pos_to_change(comb, n):
    """
    Finds the rightmost position in the comb list such that its value can
    can be increased. Returns -1 if there's no such position.
    """
    pos_to_change = len(comb) - 1
    max_possible_value = n - 1
    while pos_to_change >= 0 and comb[pos_to_change] == max_possible_value:
        pos_to_change -= 1
        max_possible_value -= 1
    return pos_to_change


def inc_value_at_pos(comb, pos):
    """
    Increments the value at the given position and generates the 
    lexicographically smallest suffix after this position.
    """
    new_comb = comb[:]
    new_comb[pos] += 1
    for idx in range(pos + 1, len(comb)):
       new_comb[idx] = new_comb[idx - 1] + 1
    return new_comb


def get_next_combination(comb, n):
    """
    Returns the lexicographically next combination or None if it doesn't
    exist.
    """
    pos_to_change = get_pos_to_change(comb, n)
    if pos_to_change < 0:
        return None
    return inc_value_at_pos(comb, pos_to_change)


def combinations(n, k):
    """
    Generates all n choose k combinations of the n natural numbers
    """
    comb = [i for i in range(k)]
    while comb is not None:
        yield comb
        comb = get_next_combination(comb, n)

It's split into several smaller functions so that it's easier to read.

A few more technical details: I used yield here to implement a generator. It's useful if the number of combinations is huge. Not storing them in a collection helps to save a lot of memory in this case (stack overflow is not the only possible issue: you can also just run out of space to store all combinations).

Note that this implementation handles corner cases properly (like k = 0).

There're a few more things you might want to add, such as parameter validation (it makes sense to throw an exception if k > n or either of them is negative).