Вот подход, который, я думаю, можно показать близким к оптимальному с точки зрения количества необходимых вычислений.Сначала я отвечу на конкретный вопрос, а затем представлю рекурсивный метод, который сгенерирует нужные комбинации для общей проблемы.
Решение конкретного вопроса
Мы видим, что естьдва массива 3-х буквенных слов.Я напишу это 2-3.Точно так же есть 2-4, 1-5, 1-6, 1-7 и 1-10.Мы можем забыть о пустом массиве.
Как можно суммировать элементы до 10?Вот возможности: 3-3-4, 3-7, 4-6, 1-10.
Нам просто нужно вычислить комбинации для каждого из них и взять их объединение.
Для 3-3-4 мы должны взять один элемент из каждого из следующих массивов:
["act", "bat", "cat"]
["boo", "con", "coo"]
["acta"] | ["tots", "tour"]
#=> ["acta", "tots", "tour"]
Мы можем использовать Array # product для вычисления этих комбинаций:
["act", "bat", "cat"].product(["boo", "con", "coo"],
["acta", "tots", "tour"])
#=> [["act", "boo", "acta"], ["act", "boo", "tots"],
# ["act", "boo", "tour"], ["act", "con", "acta"],
# ["act", "con", "tots"], ["act", "con", "tour"],
# ["act", "coo", "acta"], ["act", "coo", "tots"],
# ["act", "coo", "tour"], ["bat", "boo", "acta"],
# ["bat", "boo", "tots"], ["bat", "boo", "tour"],
# ["bat", "con", "acta"], ["bat", "con", "tots"],
# ["bat", "con", "tour"], ["bat", "coo", "acta"],
# ["bat", "coo", "tots"], ["bat", "coo", "tour"],
# ["cat", "boo", "acta"], ["cat", "boo", "tots"],
# ["cat", "boo", "tour"], ["cat", "con", "acta"],
# ["cat", "con", "tots"], ["cat", "con", "tour"],
# ["cat", "coo", "acta"], ["cat", "coo", "tots"],
# ["cat", "coo", "tour"]]
Комбинации для 3-7, 4-6 и 1-10 рассчитываются аналогично.
Рекурсивный метод для обобщенной задачи
def doit(words, target)
recurse(words.reject do |a|
a.empty? || a.first.size > target
end.sort_by { |a| a.first.size }, target)
end
def recurse(sorted, target)
arr, *rest = sorted
sz = arr.first.size
if rest.empty?
return sz == target ? arr.map { |s| [s] } : []
end
return [] if sz > target
b = recurse(rest, target) # include no element of arr
return b if sz != target && sz > target/2
case target <=> sz
when -1
b
when 0
d = arr.map { |s| [s] }
b.empty? ? d : b + d
else # 1
c = recurse(rest, target-sz)
if c.empty?
b
else
d = arr.product(c).map { |s,c| [s] + c }
b.empty? ? d : b + d
end
end
end
Еслимы выполняем
doit words, 10
решение, показанное в предыдущем разделе, возвращается, хотя элементы находятся в другом порядке.
Пояснение
Объяснениекак работают рекурсии, это сложно.На мой взгляд, лучший способ - вставить puts операторов.Одного этого, однако, недостаточно, так как быстро становится неясным, какой экземпляр метода вызывается.По этой причине я предлагаю сделать отступ, как я сделал ниже.
INDENT = 4
def indent
@offset += INDENT
puts
end
def undent
@offset -= INDENT
puts
end
def pu(str)
puts ' '*@offset + str
end
def doit(words, target)
@offset = -INDENT #***
recurse(words.reject do |a|
a.empty? || a.first.size > target
end.sort_by { |a| a.first.size }, target)
end
def recurse(sorted, target)
indent #***
puts #***
pu "sorted=#{sorted}" #***
pu "target=#{target}" #***
arr, *rest = sorted
sz = arr.first.size
pu "arr=#{arr}, rest=#{rest}, sz=#{sz}" #***
if rest.empty?
pu "returning (sz==target ? arr.map { |s| [s] } : [])="
pu "#{(sz==target ? arr.map { |s| [s] } : [])}" #***
undent #***
return sz == target ? arr.map { |s| [s] } : []
end
if sz > target
pu "returning [] as sz > target=#{sz > target}" #***
undent #***
return []
end
pu "calling recurse(#{rest}, #{target}) w/o using an element of #{arr}" #***
b = recurse(rest, target) # include no element of arr
pu "b=#{b}" #***
pu "target=#{target}, sz=#{sz}, target-sz=#{target-sz}" #***
if sz != target && sz > target/2
pu "returning b as sz != target && sz > target/2" #***
undent #***
return b
end
case target <=> sz
when -1
pu " target < sz" #***
b
when 0
pu " target == sz" #***
d = arr.map { |s| [s] }
b.empty? ? d : b + d
else # 1
pu " target > sz" #***
pu "calling recurse(#{rest}, #{target-sz}) using an element of #{arr}" #***
c = recurse(rest, target-sz)
pu "c=#{c}" #***
if c.empty?
b
else
d = arr.product(c).map { |s,c| [s] + c }
b.empty? ? d : b + d
end
end.
tap do |a|
pu "returning a=#{a}" #***
undent #***
end
end
Вот более простой пример использования.Я покажу только пример выходных данных.Заинтересованный читатель может захотеть запустить код и изучить результаты.
test_words = [["ac", "ba"], ["bo"],
["acta"], ["tots", "tour"]]
doit test_words, 8
Отображается следующее.
sorted=[["ac", "ba"], ["bo"], ["acta"], ["tots", "tour"]]
target=8
arr=["ac", "ba"], rest=[["bo"], ["acta"], ["tots", "tour"]], sz=2
calling recurse([["bo"], ["acta"], ["tots", "tour"]], 8) w/o using an element of ["ac", "ba"]
sorted=[["bo"], ["acta"], ["tots", "tour"]]
target=8
arr=["bo"], rest=[["acta"], ["tots", "tour"]], sz=2
calling recurse([["acta"], ["tots", "tour"]], 8) w/o using an element of ["bo"]
...
b=[["acta", "tots"], ["acta", "tour"]]
target=8, sz=2, target-sz=6
target > sz
calling recurse([["acta"], ["tots", "tour"]], 6) using an element of ["bo"]
sorted=[["acta"], ["tots", "tour"]]
target=6
arr=["acta"], rest=[["tots", "tour"]], sz=4
calling recurse([["tots", "tour"]], 6) w/o using an element of ["acta"]
...
c=[["tots"], ["tour"], ["acta"]]
returning a=[["bo", "tots"], ["bo", "tour"], ["bo", "acta"]]
c=[["bo", "tots"], ["bo", "tour"], ["bo", "acta"]]
returning a=[["acta", "tots"], ["acta", "tour"], ["ac", "bo", "tots"], ["ac", "bo", "tour"], ["ac", "bo", "acta"], ["ba", "bo", "tots"], ["ba", "bo", "tour"], ["ba", "bo", "acta"]]
#=> [["acta", "tots"], ["acta", "tour"],
# ["ac", "bo", "tots"], ["ac", "bo", "tour"],
# ["ac", "bo", "acta"], ["ba", "bo", "tots"],
# ["ba", "bo", "tour"], ["ba", "bo", "acta"]]