Найти комбинации в Ruby, которые меньше определенного числа

Question

Скажите, что у меня есть массив [1,2,3], и я хочу, чтобы каждая комбинация этих чисел не превышала 4. Поэтому у меня было бы [1,2, 3] .someMethod (4), и это дало бы мне:

[1,1,1,1] 
[1,1,2] 
[1,3] 
[2,2] 

до сих пор у меня есть:

(1..4).flat_map{|size| [1,2,3].repeated_combination(size).to_a } 

, но это дает мне все возможные комбинации, в том числе те, которые превышают мой заданный предел. Есть ли хороший способ либо получить только комбинации, которые соответствуют моим лимитам?

Answer 1

results = (1..4).each.with_object([]) do |size, results| 
    [1,2,3].repeated_combination(size) do |combo| 
    results << combo if combo.reduce(:+) == 4 
    end 
end 

p results 

--output:-- 
[[1, 3], [2, 2], [1, 1, 2], [1, 1, 1, 1]] 

Параметрирование алгоритм:

def do_stuff(values, target_total) 
    (1..target_total).each.with_object([]) do |size, results| 
    values.repeated_combination(size) do |combo| 
     results << combo if combo.reduce(:+) == 4 
    end 
    end 
end 

p do_stuff([1, 2, 3], 4) 

Answer 2

Вы можете отфильтровать массивы, которые вы не хотите, используя метод select. Просто выберите все массивы, которые имеют сумму == 4 (сумма рассчитывается методом inject).

all_arrs = (1..4).flat_map do |size| 
    [1,2,3].repeated_combination(size).to_a 
end 

valid_arrs = all_arrs.select do |arr| 
    arr.inject { |a, b| a + b } == 4 
end 

print valid_arrs 

# Output: 
# [[1, 3], [2, 2], [1, 1, 2], [1, 1, 1, 1]] 

Answer 3

Рекурсивный подход.

def some_method(a, n) 
    return [[]] if n == 0 

    a.select { |e| e <= n }.\ 
    flat_map { |e| some_method(a,n-e).map { |es| ([e] + es).sort } }.\ 
    sort.\ 
    uniq 
end 

p some_method([1,2,3], 4) 
# => [[1, 1, 1, 1], [1, 1, 2], [1, 3], [2, 2]] 

EDIT: Это еще одна рекурсивная версия без фильтрации дубликатов, но с противоположным порядком. Я добавил комментарии, чтобы сделать их более ясными.

def some_method(a, n) 
    return [[]] if n == 0   # bottom (solution) found 
    return [] if a.empty? || n < 0 # no solution 

    max = a.max 
    # search all solutions with biggest value 
    l = some_method(a, n-max).map { |e| [max] + e } 
    # search all solutions without biggest value 
    r = some_method(a-[max],n) 

    l + r 
end 

p some_method([1,2,3], 4) 
# => [[3, 1], [2, 2], [2, 1, 1], [1, 1, 1, 1]] 

Answer 4

arr = [1,2,3] 

(arr+[0]).repeated_combination(4).select { |a| a.reduce(:+) == 4 }.map { |a| a - [0] } 
    #=> [[1, 3], [2, 2], [1, 1, 2], [1, 1, 1, 1]] 

== Изменение к <= при желании.

Этот ответ, как и другие, принимает arr содержит натуральные числа, включая 1.