Generate all compositions of integer N into k parts

( fixed price $100 ) provide a C# function ( DOS ) to generate list all compositions of integer N into k parts this is simpler than reference below : [login to view URL] Consider the restricted compositions of 6 in four parts from integers {1,2,3}. 1 1 1 3 1 1 2 2 1 1 3 1 1 2 1 2 1 2 2 1 1 3 1 1 2 1 1 2 2 1 2 1 2 2 1 1 3 1 1 1 Is it possible to generate single composition entry without listing all? For example if I provide the set (n=6 (the number), k=4 the number of partitions, a=1, b=3 which means that each partition must be between a and b, inclusively, and i=1, meaning we're looking for the i-the lexicographically smallest composition entry) and it gives [1,1,1,3], the 1-th entry from the list. Similarly, (n=6,k=4,a=1,b=3,i=10) should return [3,1,1,1]. I searched the literature and found two algorithms but both of them enumerate all the possibilities at once. [login to view URL] [login to view URL] Knuth's TAOCP vol. 4A deals with partitions, see if you can find something that suits the problem. – gar Jul 13 '15 at 12:16 add a comment 1 Answer activeoldestvotes 2 Let the function f(n,k,a,b,i) gives the i-th lexicographically smallest partition of n into k parts, each between a and b, inclusively. I show how to compute f. Let g(n,k,a,b) be the number of partitions of n into k parts, each between a and b, inclusively. Clearly g(n,k,a,b)=∑a≤j≤bg(n−j,k−1,a,b). To compute f, first we try all the possible first entry of the partition. For each possible entry a≤j≤b, we know that there are g(n−j,k−1,a,b) partitions of n with j as its first element. Thus, we will be able to know what is the first entry of the i-th partition by finding the smallest j such that ∑a≤k≤jg(n−j,k−1,a,b)≥i. The entire partition is then j appended with f(n−j,k−1,a,b,i−∑a≤z≤j−1g(n−z,k−1,a,b)).