Generate all compositions of integer N into k parts
Budget
129$
per month
Posted: 5 years ago
Opened
- Description
- ( fixed price circa $100 ) provide a C# function ( DOS ) to generate list all compositions of integer N into k parts
this is simpler than reference below :
https://math.stackexchange.com/questions/1359342/algorithm-for-generating-restricted-integer-composition-of-n-in-k-parts-from-int
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.
http://www.mathworks.com/matlabcentral/fileexchange/27110-restricted-integer-composition
http://www.mathworks.com/matlabcentral/fileexchange/44186-restricted-integer-compositions-with-fixed-number-of-parts/content/colex.m
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)).
Skills:
algorithm development,C++ programming language,software development
- Category
Source: peopleperhour.com
Drag