如何找到所有的方法來獲得一個整數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個整數的總和（無序）？

回答

相關問題