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



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)).

Квалификация: Программирование на C#, .NET, Математика, Алгоритмы

Показать больше generate pdf reports online, generate leads debt settlement, parts mechanical drawing, how many compositions does the integer 15 have whose first part is not 1, number of ways to write n as a sum of k nonnegative integers, where the sum ranges over all compositions a1 ak of n into k parts, integer compositions proof, composition of n into odd parts, use generating functions to find the number of ways to partition 10 into odd parts, let n 2k be an even positive integer how many strong compositions of n are there into even parts, integer composition algorithm, generate real estate logo, auto parts market research, generate pdf document php, different parts simple java program, parts simple java program, commerce auto parts, car parts software database, auto parts commerce solution, generate multiple proxy windows

О работодателе:
( 70 отзыв(-а, -ов) ) London, United Kingdom

ID проекта: #22420629



C#, Unity3D, Algorithm Expert here I can do it Please send me message.

$100 USD за 2 дней(-я)
(2 отзывов(-а))

3 фрилансеров(-а) в среднем готовы выполнить эту работу за $100


Hi , I am a senior c# developer. I have rich experience with c# programming and algorithm. I can do it in one day

$100 USD за 1 день
(3 отзывов(-а))

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 за 1 день
(0 отзывов(-а))