# Generate all compositions of integer N into k parts

Budget $30-250 USD

- Freelancer
- Jobs
- C# Programming
- 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

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

## Awarded to:

## 3 freelancers are bidding on average $100 for this job

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

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!