Program to generate nCk combinations of k numbers varying from 1 to n
My function definition looks like nxt_comb = Combination(comb[1:k],n)
This function should give the next combination which comes after the input combination comb (array). The n elements of comb takes values from 1 to n.
- if function is called as a = Combination([1,3,4,6],8), then a = [1,3,4,7]
- if function is called as a = Combination([1,3,4,8],8), then a = [1,3,5,6]
- if function is called as a = Combination([1,3,7,8],8), then a = [1,4,5,6]
- if function is called as a = Combination([3,6,7,8],8), then a = [4,5,6,7]
The input combination will never be the last combination. That is, in the above case the input will be never [5,6,7,8].
Also, if the input is all zeros, the function must output the first combination that is [1,2,....,k].
Edit: What I am looking for is the logic. The implementation can be in either C/C++ or MATLAB.
Leaving aside the last requirement about starting with all 0's, which is a trivial extra check, the algorithm is:
By searching backwards, find the largest i such that comb[i]<i+n-k (using 1-based indexing; adjust if you're using C). If you can't find one, you're at the last combination.
Increment comb[i], and then working from j = i+1 up to k, set comb[j] to comb[j-i]+1