Generate all compositions of integer N into k parts

Đang Thực Hiện Đã đăng vào 4 năm trước Thanh toán khi bàn giao
Đang Thực Hiện 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)).

Lập trình C# .NET Toán học Thuật toán

ID dự án: #22420629

Về dự án

1 đề xuất Dự án từ xa 4 năm trước đang mở

1 freelancer đang chào giá trung bình $100 cho công việc này

mmojoallmighty

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!

$100 USD trong 1 ngày
(0 Nhận xét)
0.0