mathstatisticscombinationspermutationbinomial-coefficients

Find i-th combination in the list of all combinations of k positive integers that sum to n


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 need time and space complexity of at most O(k^x).

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.


Solution

  • 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]