2

我想知道是否有一种优雅的方法可以将 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实现。

4

2 回答 2

6

这是一些蟒蛇：

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)
于 2011-04-14T21:31:39.150 回答
2

2n 到 n 个非负部分的组合数（排序重要的总和）是二项式系数 C(3n-1,n-1)。例如，当 n = 2 时，C(5,1) = 5。

要看到这一点，请考虑排列 3n-1 个位置。选择其中 n-1 个的任何子集，并将“分隔符”放置在这些位置。然后，您将剩余的空白位置分组到分隔线之间的 n 组（一些可能是分隔线相邻的空组）。因此，您已经构建了所需组合与空间和分隔符的排列的对应关系，后者显然被视为一次取 n-1 件的 3n-1 个事物的组合。

为了枚举所有可能的组合，我们可以编写一个程序，从列表 [1,...,3n- 中实际选择 n-1 个严格递增的项目 s[1],...,s[n-1] 1]。根据上述，“部分”将是 x[i] = s[i] - s[i-1] - 1 for i = 1,...,n 约定 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 程序，它给出了 N 使用 P 非负部分的更一般的组合列表：

/* 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将其第一个参数表示为以第二个参数为长度的非负整数列表（第三个参数）的总和。

该定义需要几个实用谓词，这些谓词通常由实现提供，形式可能略有不同。为完整起见，计数谓词for/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).
于 2011-04-15T13:37:23.853 回答