使用嵌套循環的分佈

Question

我想編寫一個程序來生成給定n的所有分佈。

例如，如果我輸入n等於7，返回的結果將是：

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

我寫了下面的代碼：

def sum(a, n) 
    for i in 1..a.length 
    a.each do |a| 
     z = a+i 
     if z == n 
     print i 
     puts a 
     end 
    end 
    end 
end 

def distribution(n) 
    numbers_container = [] 
    for i in 1..n-1 
    numbers_container<<i 
    end 
    sum(numbers_container,n) 
end 

puts "Enter n" 
n = gets.chomp.to_i 
distribution(n) 

我被困在部分的地方程序需要檢查超過兩個augends的總和。我不知道如何編寫第二個循環。

Answer 1

我建議你使用遞歸。

代碼

def all_the_sums(n, mx=n, p=[]) 
    return [p] if n.zero? 
    mx.downto(1).each_with_object([]) { |i,a| 
    a.concat(all_the_sums(n-i, [n-i,i].min, p + [i])) } 
end 

例

all_the_sums(7) 
    #=> [[7], 
    # [6, 1], 
    # [5, 2], [5, 1, 1], 
    # [4, 3], [4, 2, 1], [4, 1, 1, 1], 
    # [3, 3, 1], [3, 2, 2], [3, 2, 1, 1], [3, 1, 1, 1, 1], 
    # [2, 2, 2, 1], [2, 2, 1, 1, 1], [2, 1, 1, 1, 1, 1], 
    # [1, 1, 1, 1, 1, 1, 1]] 

說明

的參數mx是避免結果permuations的產生。例如，一個序列是[4,2,1]。這個數組有六個排列組合（例如，[4,1,2],[2,4,1]等等），但我們只需要一個。

現在考慮執行的計算：

all_the_sums(3) 

每八個空格縮進下面反映了該方法的遞歸調用。

我們與

n = 3 
mx = 3 
p = [] 

return [[]] if 3.zero? #=> no return 
# first value passed block by 3.downto(1).. 
i = 3 
a = [] 
# invoke all_the_sums(0, [0,3].min, []+[3]) 

     all_the_sums(0, 0, [3]) 
     return [[3]] if 0.zero? #=> return [[3]] 

a.concat([[3]]) #=> [].concat([[3]]) => [[3]] 
# second value passed block by 3.downto(1).. 
i = 2 
a = [[3]] 
# invoke all_the_sums(1, [1,2].min, []+[2]) 

     all_the_sums(1, 1, [2]) 
     return [[2]] if 1.zero? #=> do not return 
     # first and only value passed block by 1.downto(1).. 
     i = 1 
     a = [] 
     # invoke all_the_sums(0, [0,1].min, [2]+[1]) 

       all_the_sums(0, 0, [2,1]) 
       return [[2,1]] if 0.zero? #=> [[2,1]] returned 

     a.concat([[2,1]]) #=> [].concat([[2,1]]) => [[2,1]] 
     return a #=> [[2,1]] 

a.concat([[2,1]]) #=> [[3]].concat([[2,1]]) => [[3],[2,1]] 
# third and last value passed block by 3.downto(1).. 
i = 1 
a = [[3],[2,1]] 
# invoke all_the_sums(2, [2,1].min, [1]) 

     all_the_sums(2, 1, [1]) 
     return [] if 2.zero? #=> [] not returned 
     # first and only value passed block by 1.downto(1).. 
     i = 1 
     a = [] 
     # invoke all_the_sums(1, [1,1].min, [1]+[1]) 

       all_the_sums(1, 1, [1,1]) 
       return [1,1] if 1.zero? #=> [1,1] not returned 
       # first and only value passed block by 1.downto(1).. 
       i = 1 
       a = [] 
       # invoke all_the_sums(0, [0,1].min, [1,1]+[1]]) 

         all_the_sums(0, 0, [1,1,1]) 
         return [1,1,1] if 1.zero? 
          #=> return [1,1,1] 

       a.concat([[1,1,1]]) #=> [[1,1,1]] 
       return a #=> [[1,1,1]] 

     a.concat([[1,1,1]]) #=> [].concat([[1,1,1]]) => [[1,1,1]] 
     return a #=> [[1,1,1]] 

a.concat([[1,1,1]]) #=> [[3],[2,1]].concat([[1,1,1]]) 
return a #=> [[3],[2,1],[1,1,1]] 

Answer 2

您可以使用一元與parameters有參數無限量：

def test_method *parameters 
    puts parameters 
    puts parameters.class 
end 

test_method("a", "b", "c", "d") 

所以，parameters塊內成爲一組參數。然後，您可以伊斯利循環通過他們：

parameters.each { |par| p par } 

另外，不要使用for循環這個，因爲它們比使用each方法的可讀性。

[1..n-1].each do i 
    # body omitted 
end 

Answer 3

我覺得如果您試圖以遞歸方式調用sum，就可以解決這個問題。

print i 
puts a 

重新嘗試呼叫sum，像這樣：

sum((1..a).to_a, a) 

它不會解決它，但它可能會導致你在正確的方向，該位之後。