java - 如何将 2n 表示为 n 个变量的总和(Java 实现？)

Question

我想知道是否有一种优雅的方式来导出所有 compositions 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。

更一般地，问题可以表述为找到 n 个非负整数变量的 s 的所有组成，它们的总和等于 s。

任何有关如何有效计算此问题的建议都将受到欢迎，并且非常感谢一些伪代码。谢谢。

编辑:虽然下面介绍了 Perl 和 Prolog 中的解决方案，但 Java 实现可能会出现新问题，因为线性数据结构(例如数组)需要在递归调用期间传递和操作，并且随着 n 变大，这种做法会变得非常昂贵，我想知道是否有替代的(并且更有效的)Java 实现来解决这个问题。

Answer 1

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