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

Question

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.

Answer 1

• you need to use divide-and-conquer algorithm where you breaks down a problem into two or more sub-problems until these become simple enough to be solved directly.

• use the value of i to find the answer that you want.

the number of solutions where the first element is j is :

   C(n-2-(j-1),k-2) , where 1 <= j <= n-k+1

for example :

the number of solutions where the first element is 1 is 5 :

[1, 1, 5], [1, 2, 4], [1, 3, 3],[1, 4, 2],[1, 5, 1]

C(7-2-(1-1),3-2) = C(5,1) 
                 = 5 

we can find the value of the first element by comparing :

• the value of i and the sum of C(n-2-(j-1),k-2) from 1 to j

  j	C(n-2-(j-1) )	sum of C(n-2-(j-1),k-2) from 1 to j
  1	C(5,1)=5	5
  2	C(4,1)=4	9
  3	C(3,1)=3	12
  4	C(2,1)=2	14
  5	C(1,1)=1	15

starting from j=1, j is the first element when : i < sum C(n-2-(j-1),k-2) from 1 to j

after finding the value of the first element, repeat the process but for:

• n = n - j
• k = k - 1
• i -=sum C(n-2-(j-1),k-2) from 1 to j

until k = 1 , then you can get the last element by substract n from the sum of all the elements that we found

input : 
    find(7,3,5)
output : 
    [ 2, 1, 4 ]

code in javascript :

// combination nCp
function C(n, k) {
   k = Math.min(n, n - k)
   let ans = 1
   while (k > 0) {
       ans *= n - k + 1
       ans /= k
       k--
   }
   return Math.round(ans)
}

function find(n, k, i) {

   let list = [] // store the answer
   let sum = 0
   let Max = C(n - 1, k - 1) // number of solutions

   // is i or k is illegal ?
   if (Max < i || k > n)
       return null

   function getValue(n, k, i) {

       // is one element left to find the answer ?
       if (k === 1)
           return

       let value = C(n - 2, k - 2) // number of solutions where the first element is 1
       let j = 0;
       while (i >= value) {
           i -= value

           // calculate C(n-2-1,k-2-1) without using Combination function
           value *=n-k-j
           value /=n-2-j
           j++
       }

       list.push(j + 1) //element of solution found
       sum += j + 1
       getValue(n - j - 1, k - 1, i) // solve the sub-problem
   }

   getValue(n, k, i)
   list.push(n-sum)// add the last element
   return list
}

let n = 7
let k = 3
let i = 5

console.log(find(n, k, i));

Answer 2

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]