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.