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:
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.
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]