如何找到所有的方法来获得一个整数n为m个整数的总和（无序）？

我正在寻找一种算法，找到所有的方式来表示整数n作为m（非负）整数的总和。我特别感兴趣的是m = 6和n⩽20。找到所有可能性的最快方式是什么（使用计算机，而不是手工）。如果可能的话，我只想看看六个整数的组合，顺序不相关（即[1,2,0,0,0,0]和[2,1,0,0,0,0 ]计为1个组合）。如何找到所有的方法来获得一个整数n为m个整数的总和（无序）？

最简单的方法是简单地尝试使用小于或等于20的6个整数进行所有置换，并且只添加总和为20的结果（如果我们不想查看顺序，则删除双精度））。这似乎要花很长的时间，因为20^6的可能性需要很长时间才能检查。

什么是更有效的方法来解决这个问题？

来源

2017-01-24 Dasherman

提示：避免重复可以很容易，如果你在排序顺序生成它们来完成。如果你有m个数字来填充，以便他们总计为n并且数字是递增的，那么第一个数字有什么可能性？ –

您可以通过以单调递增的顺序生成数字（每个数字等于或大于前一个数字）来避免重复。

对于给定的count（例如6），您可以递归地定义问题，方法是为第一个数字生成所有可能的值，然后递归地生成所有count - 1数字的列表，其总和减去第一个数字，第一个数字是列表中剩余数字的最小值。

因为数字需要增加，所以不能“过早达到峰值” - 您可以通过将总和除以计数来计算最大值（因为所有剩余的值必须等于或大于此值）。

这里是一个简单的Java实现：

public static void outputSums(String start, int sum, int count, int min) 
{ 
    // if there is just one value, it's just the sum: 
    if(count == 1) 
    { 
     System.out.println(start + " " + sum); 
     return; 
    } 

    int max = sum/count; // calculate maximum value 
    for(int i = min; i <= max; i++) 
    { 
     outputSums(start + " " + i, // append each number to the list 
      sum - i, // recursively find numbers that sum to the remainder 
      count - 1, // with a count of one less 
      i); // equal to or greater to this one (i.e. increasing order) 
    } 
}

start包含有输出的到目前为止的部分名单。当你第一次调用函数时它将是空的。

Demo

来源

2017-01-24 21:11:18 samgak

以前的做法相反的是它计算从最大到最小。

这是一个Python的实现，它使用迭代器，因此它很容易以编程方式使用。

def partition (count, total, maximum = None) : 
    if maximum is None or total < maximum: 
     maximum = total 
    if 0 == count: 
     yield [] 
    else: 
     while total <= count * maximum: 
      for part in partition(count - 1, total - maximum, maximum): 
       yield part + [maximum] 
      maximum = maximum - 1

这里是如何使用它编程来打印输出的例子：

for part in partition(6, 10): 
    print(part)

来源

2017-01-24 22:42:58 btilly

如何找到所有的方法来获得一个整数n为m个整数的总和（无序）？

回答

相关问题