I wonder if there is an elegant way to derive all compositions of 2n as the sum of n non-negative integer variables.

For example, for n = 2 variables x and y, there are 5 compositions with two parts :

x = 0 y = 4; x = 1 y = 3; x = 2 y = 2; x = 3 y = 1; x = 4 y = 0

such that x + y = 4 = 2n.

More generally, the problem can be formulated to find all the compositions of s into n non-negative integer variables with their sum equals to s.

Any suggestion on how to compute this problem efficiently would be welcome, and some pseudo-code would be much appreciated. Thanks.

Edit: while solutions are presented below as in Perl and Prolog, a **Java** implementation may present a new problem as linear data structures such as arrays need to be passed around and manipulated during the recursive calls, and such practice can become quite expensive as n gets larger, I wonder if there is an alternative (and more efficient) **Java** implementation for this problem.

-------------Problems Reply------------

Here's some python:

`def sumperms(n, total = None):`

if total == None:

# total is the target sum, if not specified, set to 2n

total = 2 * n

```
```if n == 1:

# if n is 1, then there is only a single permutation

# return as a tuple.

# python's syntax for single element tuple is (element,)

yield (total,)

return

# iterate i over 0 ... total

for i in range(total + 1):

# recursively call self to solve the subproblem

for perm in sumperms(n - 1, total - i):

# append the single element tuple to the "sub-permutation"

yield (i,) + perm

`# run example for n = 3`

for perm in sumperms(3):

print perm

Output:

`(0, 0, 6)`

(0, 1, 5)

(0, 2, 4)

(0, 3, 3)

(0, 4, 2)

(0, 5, 1)

(0, 6, 0)

(1, 0, 5)

(1, 1, 4)

(1, 2, 3)

(1, 3, 2)

(1, 4, 1)

(1, 5, 0)

(2, 0, 4)

(2, 1, 3)

(2, 2, 2)

(2, 3, 1)

(2, 4, 0)

(3, 0, 3)

(3, 1, 2)

(3, 2, 1)

(3, 3, 0)

(4, 0, 2)

(4, 1, 1)

(4, 2, 0)

(5, 0, 1)

(5, 1, 0)

(6, 0, 0)

The number of compositions (sums where ordering matters) of 2n into exactly n non-negative parts is the binomial coefficient C(3n-1,n-1). For example, with n = 2 as above, C(5,1) = 5.

To see this, consider lining up 3n-1 positions. Choose any subset of n-1 of these, and place "dividers" in those positions. You then have the remaining blank positions grouped into n groups between dividers (some possibly empty groups where dividers are adjacent). Thus you have constructed a correspondance of the required compositions with the arrangements of spaces and dividers, and the latter is manifestly counted as combinations of 3n-1 things taken n-1 at a time.

For the purpose of enumerating all the possible compositions we could write a program that actually selects n-1 strictly increasing items s[1],...,s[n-1] from a list [1,...,3n-1]. In accordance with the above, the "parts" would be x[i] = s[i] - s[i-1] - 1 for i = 1,...,n with the convention that s[0] = 0 and s[n] = 3n.

More elegant for the purpose of listing compositions would be to select n-1 weakly increasing items t[1],...,t[n-1] from a list [0,...,2n] and calculate the parts x[i] = t[i] - t[i-1] for i = 1,...,n with the convention t[0] = 0 and t[n] = 2n.

Here's a brief Prolog program that gives the more general listing of compositions of N using P non-negative parts:

`/* generate all possible ordered sums to N with P nonnegative parts */`

```
```composition0(N,P,List) :-

length(P,List),

composition0(N,List).

`composition0(N,[N]).`

composition0(N,[H|T]) :-

for(H,0,N),

M is N - H,

composition0(M,T).

The predicate **compostion0/3** expresses its first argument as the sum of a list of non-negative integers (third argument) having the second argument as its length.

The definition requires a couple of utility predicates that are often provided by an implementation, perhaps in slightly different form. For completeness a Prolog definition of the counting predicate **for/3** and length of list predicate are as follows:

`for(H,H,N) :- H =< N.`

for(H,I,N) :-

I < N,

J is I+1,

for(H,J,N).

```
```length(P,List) :- length(P,0,List).

`length(P,P,[ ]) :- !.`

length(P,Q,[_|T]) :-

R is Q+1,

length(P,R,T).