# 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 :

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.

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

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

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

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

ID проекта: #22420629

## Поручен:

monkeyMatrix

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

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

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

polite90

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