I want to implement a function that takes 3 params: n, k and i. The function should return the i-th combinations of k positive integers numbers that sum to n. The function, internally, should not generate all the possible combinations before returning the i-th. The function should be able to generate the combination without generating all the others; in other terms, time complexity should be at most O(k).

For example:

Input: n=7, k=3, i=5
Output: [2, 1, 4]

This is because all possible combinations of k=3 positive elements that sum to n=7 are

    0= [1, 1, 5]
    1= [1, 2, 4]
    2= [1, 3, 3]
    3= [1, 4, 2]
    4= [1, 5, 1]
    5= [2, 1, 4]
    6= [2, 2, 3]
    7= [2, 3, 2]
    8= [2, 4, 1]
    9= [3, 1, 3]
    10=[3, 2, 2]
    11=[3, 3, 1]
    12=[4, 1, 2]
    13=[4, 2, 1]
    14=[5, 1, 1]

So, the combination at index 5 is [2,1,4].

Additional informations:

1. I can already generate the total number of possible combinations for a given k and n. This can be done computing the binomial coefficent of Coeff(n-1, k-1).
   Here you can find more info about this. I imagine that in some way, if you
   want to generate only the i-th combination (without generating the
   others), you should need to calculate the total number of
   combinations
2. I already checked this stackoverflow answer but the problem is a bit different and I am not able to adapt the answer to my scenario. I also checked the referred wikipedia page: I think it's gold. It contains info about ordering combinations, getting the index for a given combination and also the reverse process, getting the combination based on its index (that is what I need).
3. "Ascending order" is not important in my scenario. If combinations were enumerated in reverse order (look at my previous example), the function for n=7, k=3, i=5 should return [3,1,3] (starting from the last combination). This is acceptable for me.
4. It would be great if you provide a short explanation and a short piece of code as well. Javascript is the language I can better understand but if you are familiar with other languages I will try to understand anyway :)
5. About time complexity: I asked for an O(k). If the function internally should compute the binomial coefficient several time, you can consider the complexity of calling the binomial coefficient function as O(k).

I tried googling and using the stackoverflow answer I linked in point 2 with no luck (I also wrote an implementation of the proposed algorithm). My scenario is slightly different and I don't have the math/statistic skill to solve the problem by myself.

CodePudding user response：

As far as I understand, you can generate combination by its index in range 0..Coeff(n-1, k-1)-1.

Having this combination (as list/array comb), we can construct corresponding partition of n using "stars and bars" principle - n stars, k-1 bars between them

Full code in Python:

def cnk(n, k):
    k = min(k, n - k)
    if k <= 0:
        return 1 if k == 0 else 0
    res = 1
    for i in range(k):
        res = res * (n - i) // (i   1)
    return res

def num2comb(n, k, m):  #combination by its number in lex. order
    res = []
    next = 1
    while k > 0:
        cn = cnk(n - 1, k - 1)
        if m < cn:
            res.append(next)
            k -= 1
        else:
            m -= cn
        n -= 1
        next  = 1
    return res

n = 8
k = 4
m = 10
comb = num2comb(n-1, k-1, m)
print(comb)
partition = [comb[0]]
for i in range(1, len(comb)):
    partition.append(comb[i]-comb[i-1])
partition.append(n - comb[-1])
print(partition)

Intermediate helper object

>>>[1, 4, 6]

Resulting partition

>>>[1, 3, 2, 2]