如何将2n表示为n个变量的总和（Java实现？）

| 我想知道是否有一种优雅的方法可以将2n的所有成分导出为n个非负整数变量的总和。例如，对于n = 2个变量x和y，有5个成分分为两部分： x = 0 y = 4; x = 1 y = 3; x = 2 y = 2; x = 3 y = 1; x = 4 y = 0 这样x + y = 4 = 2n。更一般而言，可以制定问题以将s的所有组成都找到n个非负整数变量，它们的和等于s。任何有关如何有效计算此问题的建议都将受到欢迎，一些伪代码将不胜感激。谢谢。编辑：虽然下面在Perl和Prolog中介绍了解决方案，但是Java实现可能会出现一个新问题，因为在递归调用期间需要传递和操纵线性数据结构（例如数组），并且随着n的获得，这种做法会变得非常昂贵更大，我想知道是否存在替代（更有效）的Java实现来解决此问题。

已邀请:

2 个回复

葛瞎说漓

这是一些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

输出：

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

骚瓤

恰好在n个非负部分中的2n的合成数量（排序重要的和）为二项式系数C（3n-1，n-1）。例如，如上所述，当n = 2时，C（5,1）= 5。要看到这一点，请考虑排列3n-1个位置。选择其中n-1个子集，然后将“ dividers”放在这些位置。然后，将剩余的空白位置分为两个分隔符之间的n个组（分隔符相邻的一些空组）。因此，您已经构造了所需组成与空间和分隔线的对应关系，并且分隔线显然被算作一次取n-1的3n-1个事物的组合。为了列举所有可能的组成，我们可以编写一个程序，实际上从列表[1，...，3n-中选择n-1个严格增加的项s [1]，...，s [n-1]。 1]。根据上述规定，对于“ i = 1，...，n”，“ parts”将为x [i] = s [i]-s [i-1]-1（按s [0]的约定） = 0且s [n] = 3n。出于列出成分的目的，更优雅的方法是从列表[0，...，2n]中选择n-1个微增项t [1]，...，t [n-1]并计算部分x [i] = t [i]-t [i-1]，其中i = 1，...，n，约定t [0] = 0且t [n] = 2n。这是一个简短的Prolog程序，它使用P个非负数部分提供了N的更一般的列表：

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

谓词compostion0 / 3将其第一个自变量表示为以第二个自变量为长度的非负整数列表（第三个自变量）的总和。该定义需要一些实用程序谓词，这些谓词通常由实现提供，可能形式略有不同。为了完整性，对于/ 3的计数谓词和列表谓词的长度的Prolog定义如下：

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

要回复问题请先登录或注册

如何将2n表示为n个变量的总和（Java实现？）

2 个回复

发起人

math

java

algorithm

subset_sum

composition

问题状态

如何将2n表示为n个变量的总和（Java实现？）

与内容相关的链接

2 个回复

发起人

math

java

algorithm

subset_sum

composition

问题状态