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).
精彩评论