打印所有方法來總計n個整數，以便它們總計給定的總和。

Question

我試圖想出一個算法，將打印出所有可能的方法來總結N個整數，以便他們總計一個給定的值。

例子。打印所有的方式來總結的4個整數，使他們總結爲5。

結果應該是這樣的：

5 0 0 0 
4 1 0 0 
3 2 0 0 
3 1 1 0 
2 3 0 0 
2 2 1 0 
2 1 2 0 
2 1 1 1 
1 4 0 0 
1 3 1 0 
1 2 2 0 
1 2 1 1 
1 1 3 0 
1 1 2 1 
1 1 1 2 

Answer 1

這是基於Alinium的代碼。
我修改了它以便打印出所有可能的組合，因爲他已經完成了所有的排列組合。
此外，我不認爲你需要for循環時，n = 1，因爲在這種情況下，只有一個數字應該導致總和等於價值。
各種其他修改，以獲得邊界案件的工作。

def sum(n, value): 
    arr = [0]*n # create an array of size n, filled with zeroes 
    sumRecursive(n, value, 0, n, arr); 

def sumRecursive(n, value, sumSoFar, topLevel, arr): 
    if n == 1: 
     if sumSoFar <= value: 
      #Make sure it's in ascending order (or only level) 
      if topLevel == 1 or (value - sumSoFar >= arr[-2]): 
       arr[(-1)] = value - sumSoFar #put it in the n_th last index of arr 
       print arr 
    elif n > 0: 
     #Make sure it's in ascending order 
     start = 0 
     if (n != topLevel): 
      start = arr[(-1*n)-1] #the value before this element 

     for i in range(start, value+1): # i = start...value 
      arr[(-1*n)] = i # put i in the n_th last index of arr 
      sumRecursive(n-1, value, sumSoFar + i, topLevel, arr) 

乳寧款項（4，5）返回：
[0，0，0，5]
[0,0，1,4]
[0,0，2，3]
[0，1，1，3]
[1，1，1，2]

Answer 2

我沒有測試過這一點：

 
    procedure allSum (int tot, int n, int desiredTotal) return int 
     if n > 0 
      int i = 
      for (int i = tot; i>=0; i--) { 
       push i onto stack; 
       allSum(tot-i, n-1, desiredTotal); 
       pop top of stack 
      } 
     else if n==0 
      if stack sums to desiredTotal then print the stack end if 
     end if 

我肯定有更好的方法來做到這一點。

Answer 3

解決這個問題的關鍵是遞歸。這是一個在python中的工作實現。它打印出所有可能的排列總和。你可能想要擺脫重複的組合，可能通過使用一些Set或hashing機制來濾除它們。

def sum(n, value): 
    arr = [0]*n # create an array of size n, filled with zeroes 
    sumRecursive(n, value, 0, n, arr); 

def sumRecursive(n, value, sumSoFar, topLevel, arr): 
    if n == 1: 
     if sumSoFar > value: 
      return False 
     else: 
      for i in range(value+1): # i = 0...value 
       if (sumSoFar + i) == value: 
        arr[(-1*n)] = i # put i in the n_th last index of arr 
        print arr; 
        return True 

    else: 
     for i in range(value+1): # i = 0...value 
      arr[(-1*n)] = i # put i in the n_th last index of arr 
      if sumRecursive(n-1, value, sumSoFar + i, topLevel, arr): 
       if (n == topLevel): 
        print "\n" 

經過一些額外的努力，這可能會被簡化爲擺脫我傳遞給遞歸函數的一些參數。正如redcayuga的僞代碼所暗示的那樣，使用堆棧而不是手動管理數組，將是一個更好的主意。

Answer 4

在純數學，求和整數以獲得給定的總的一種方式被稱爲分區。如果你是谷歌的「整數分區」，有很多信息。您正在尋找具有特定數量的元素的整數分區。我相信你可以採用其中一種已知的生成機制並適應這種額外的情況。維基百科對主題Partition_(number_theory)有很好的概述。 Mathematica甚至有一個功能可以做你想做的事情：IntegerPartitions[5, 4]。

Answer 5

我發現基於Alinium代碼

class Domain_partition 

    attr_reader :results, 
       :domain, 
       :sum, 
       :size 

    def initialize(_dom, _size, _sum) 
     _dom.is_a?(Array) ? @domain=_dom.sort : @domain= _dom.to_a 
     @results, @sum, @size = [], _sum, _size 
     arr = [0]*size # create an array of size n, filled with zeroes 
     sumRecursive(size, 0, arr) 
    end 

    def sumRecursive(n, sumSoFar, arr) 

     if n == 1 
      #Make sure it's in ascending order (or only level) 
      if sum - sumSoFar >= arr[-2] and @domain.include?(sum - sumSoFar) 
       final_arr=Array.new(arr) 
       final_arr[(-1)] = sum - sumSoFar #put it in the n_th last index of arr 
       @results<<final_arr 
      end 

     elsif n > 1 

      #********* dom_selector ******** 

      n != size ? start = arr[(-1*n)-1] : start = domain[0] 
      dom_bounds=(start*(n-1)..domain.last*(n-1)) 

      restricted_dom=domain.select do |x| 

       if x < start 
        false; next 
       end 

       if size-n > 0 
        if dom_bounds.cover? sum-(arr.first(size-n).inject(:+)+x) then true 
        else false end 
       else 
        dom_bounds.cover?(sum+x) ? true : false 
       end 
      end # *************************** 

      for i in restricted_dom 
       _arr=Array.new(arr) 
       _arr[(-1*n)] = i 
       sumRecursive(n-1, sumSoFar + i, _arr) 
      end 
     end 
    end 
end 

a=Domain_partition.new (-6..6),10,0 
p a 

b=Domain_partition.new [-4,-2,-1,1,2,3],10,0 
p b 

Answer 6

如果你有興趣的產生與域說明紅寶石的方式（詞彙）下令整數分區，即獨特的無序組Si的正整數（無0的）總和爲N，然後嘗試以下。 （無序簡單地意味着[1,2,1]和[1,1,2]是相同的分區）

該問題不需要遞歸，因爲查找下一個詞法限制分區其實很簡單...

概念：從最後一個加數（整數）開始，查找兩個加數之間的差值大於1的第一個實例。在此處將分割分爲兩部分。從較高的整數（這將是一個部分中的最後一個整數）中刪除1，並將較低的整數（後一部分的第一個整數）加1。然後找到後面部分的第一個詞法順序分區，它將新的最大整數作爲最大加數值。我使用Sage找到第一個詞法分區，因爲它的速度很快，但沒有它就很容易完成。最後，加入這兩部分，瞧！你有N個S部分的下一個詞法分區。

例如[6,5,3,2,2] - > [6,5]，[3,2,2] - > [6,4]，[4,2,2] - > [6,4]，[ 4,3,1] - > [6,4,4,3,1]

因此，在Python和調用賢者的小任務，找到第一個詞法分區給定n和s部分...

from sage.all import * 

def most_even_partition(n,s): # The main function will need to recognize the most even partition possible (i.e. last lexical partition) so it can loop back to the first lexical partition if need be 
    most_even = [int(floor(float(n)/float(s)))]*s 
    _remainder = int(n%s) 

    j = 0 
    while _remainder > 0: 
     most_even[j] += 1 
     _remainder -= 1 
     j += 1 
    return most_even 

def portion(alist, indices): 
    return [alist[i:j] for i, j in zip([0]+indices, indices+[None])] 


def next_restricted_part(p,n,s): 
    if p == most_even_partition(n,s):return Partitions(n,length=s).first() 

    for i in enumerate(reversed(p)): 
     if i[1] - p[-1] > 1: 
      if i[0] == (s-1): 
       return Partitions(n,length=s,max_part=(i[1]-1)).first() 
      else: 
       parts = portion(p,[s-i[0]-1]) # split p (soup?) 
       h1 = parts[0] 
       h2 = parts[1] 
       next = list(Partitions(sum(h2),length=len(h2),max_part=(h2[0]-1)).first()) 
       return h1+next 

如果你想要零（不是實際的整數分區），那麼這些函數只需要很小的修改。

Answer 7

試試看看這個代碼。我希望它更容易理解。我測試了它，它產生了正確的序列。

void partition(int n, int m = 0) 
{ 
    int i; 
    // if the partition is done 
    if(n == 0){ 
     // Output the result 
     for(i = 0; i < m; ++i) 
      printf("%d ", list[i]); 
     printf("\n"); 
     return; 
    } 
    // Do the split from large to small int 
    for(i = n; i > 0; --i){ 
     // if the number not partitioned or 
     // willbe partitioned no larger than 
     // previous partition number 
     if(m == 0 || i <= list[m - 1]){ 
      // store the partition int 
      list[m] = i; 
      // partition the rest 
      partition(n - i, m + 1); 
     } 
    } 
} 

要求澄清，如果需要的話。

的是一個輸出

6 
5 1 
4 2 
4 1 1 
3 3 
3 2 1 
3 1 1 1 
2 2 2 
2 2 1 1 
2 1 1 1 1 
1 1 1 1 1 1 


10 
9 1 
8 2 
8 1 1 
7 3 
7 2 1 
7 1 1 1 
6 4 
6 3 1 
6 2 2 
6 2 1 1 
6 1 1 1 1 
5 5 
5 4 1 
5 3 2 
5 3 1 1 
5 2 2 1 
5 2 1 1 1 
5 1 1 1 1 1 
4 4 2 
4 4 1 1 
4 3 3 
4 3 2 1 
4 3 1 1 1 
4 2 2 2 
4 2 2 1 1 
4 2 1 1 1 1 
4 1 1 1 1 1 1 
3 3 3 1 
3 3 2 2 
3 3 2 1 1 
3 3 1 1 1 1 
3 2 2 2 1 
3 2 2 1 1 1 
3 2 1 1 1 1 1 
3 1 1 1 1 1 1 1 
2 2 2 2 2 
2 2 2 2 1 1 
2 2 2 1 1 1 1 
2 2 1 1 1 1 1 1 
2 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1