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

Question

我想知道是否有一种优雅的方法来推导出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实现可能会出现一个新问题,因为线性数据结构(如数组)需要在递归调用期间传递和操作,并且这样的实践可能会变得非常昂贵更大,我想知道是否有替代(并且更有效)的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)