# How to express 2n as sum of n variables (Java implementation?)

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,...,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 and s[n] = 3n.

More elegant for the purpose of listing compositions would be to select n-1 weakly increasing items t,...,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 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). ```

Category:java Views:0 Time:2011-04-14

## Related post

Copyright (C) dskims.com, All Rights Reserved.

processed in 0.175 (s). 11 q(s)