數組中元素的隨機和等於y - ruby​​

Question

需要創建一個數組，其總數應該等於期望值。

inp = [1,2,3,4,5,6,7,8,9,10] 
sum = 200 

輸出：

out = [10,10,9,1,3,3,3,7,.....] whose sum should be 200 
or 
out = [10,7,3,....]    Repeated values can be used 
or 
out = [2,3,4,9,2,....] 

我想作爲，

arr = [5,10,15,20,30] 
ee = [] 
max = 200 
while (ee.sum < max) do 
    ee << arr.sample(1).first 
end 

ee.pop(2) 
val = max - ee.sum 
pair = arr.uniq.combination(2).detect { |a, b| a + b == val } 
ee << pair 
ee.flatten 

有沒有做任何有效的方法。

Answer 1

inp = [1,2,3,4,5,6,7,8,9,10] 
sum = 20 

inp.length.downto(1).flat_map do |i| 
    inp.combination(i).to_a # take all subarrays of length `i` 
end.select do |a| 
    a.inject(:+) == sum  # select only those summing to `sum` 
end 

可能需要random結果數組的元素。

result = inp.length.downto(1).flat_map do |i| 
    inp.combination(i).to_a # take all subarrays of length `i` 
end.select do |a| 
    a.inject(:+) == sum  # select only those summing to `sum` 
end 
puts result.length 
#⇒ 31 
puts result.sample 
#⇒ [2, 4, 5, 9] 
puts result.sample 
#⇒ [1, 2, 3, 6, 8] 
... 

請注意，這種方法對長輸入無效。同樣，如果任何原始陣列的成員可能會被拍攝很多次，上面的combination應更改爲permutation，但這種解決方案太無效，無法與permutation一起使用。

Answer 2

我發現下面的鏈接這一問題的回答：

Finding all possible combinations of numbers to reach a given sum

def subset_sum(numbers, target, partial=[]) 
s = partial.inject 0, :+ 
#check if the partial sum is equals to target 
puts "sum(#{partial})=#{target}" if s == target 
return if s >= target #if we reach the number why bother to continue 
(0..(numbers.length - 1)).each do |i| 
    n = numbers[i] 
    remaining = numbers.drop(i+1) 
    subset_sum(remaining, target, partial + [n]) 
end 
end 

subset_sum([1,2,3,4,5,6,7,8,9,10],20)