Generate all compositions of integer N into k parts
$30-250 USD
Thanh toán khi bàn giao
( 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)).
ID dự án: #22420629
Về dự án
1 freelancer đang chào giá trung bình $100 cho công việc này
Hi there. Alongside with my 8 years of experience in web development, I can easily build any algorithm based on sorts, numbers of partitions or arrays. Looking forward to work with you. Have a great day!