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开发者_Python百科-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.

---

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