Алгоритмы Все построены на Ruby
Я застрял в этом алгоритме, результат не такой, как я ожидал, цель состоит в том, чтобы получить все возможные способы внутри массива в 2D-массив, объединяющий возможное множественное решение для воссоздания данной цели.
Ожидаемый результат
[
["purp", "le"]
["p","ur", "p", "le"]
]
Выход []
def all_contruct(target, wordBank)
return [[]] if target == ''
result = []
wordBank.each do |word|
if target.index(word) == 0
suffix = target.slice(word.length)
suffixResult = all_contruct(suffix, wordBank)
suffixWay = suffixResult.map { |e| [ word, *e] }
result.push(*suffixWay)
end
end
return result
end
all_contruct("purple",["purp","p","ur","le","purpl"])
#=> []
это ожидаемый результат: [["purp", "le"] ["p", "ur", "p", "le"]]
Сначала вам нужно объяснить, что вы пытаетесь сделать, без ссылки на ваш код. При этом было бы полезно включить небольшой пример. Примеры должны включать входные данные, показанные как один или несколько объектов Ruby, и ожидаемое возвращаемое значение, также как объект Ruby. Полезно назначить переменную каждому входу (например, arr = [1,2,..]). Таким образом, читатели могут ссылаться на эти переменные (arr) в ответах и комментариях.
В вашей последней строке приведен пример, но вам нужно переместить его, чтобы он предшествовал вашему коду, объяснил значение каждого из двух аргументов метода (второй - это массив строк) и, что важно, показать желаемое возвращаемое значение для этих двух аргументы.
Спасибо @CarySwoveland за ваше предложение, я буду придерживаться его, надеюсь, кто-то уже помог мне, и ответ ниже, если у кого-то еще есть такая же проблема.
Вот простое, но относительно неэффективное по времени (но компактное) решение: word = "purple"; arr = ["purp", "p", "ur", "le", "purpl"]; (1..arr.size).each_with_object([]) { |n,ar| arr.repeated_permutation(n) { |a| ar << a if a.join == word } } #=> [["purp", "le"], ["p", "ur", "p", "le"]]. См. Массив # повторная_перестановка.
Однако лучше использовать рекурсию, как это сделал @Fravadona. Рекурсивный метод можно также записать следующим образом: def doit(word, arr, root = []); arr.each_with_object([]) do |w,a|; new_root = root + [w]; new_word = new_root.join; if new_word == word; a << new_root; elsif word.start_with?(new_word); doit(word, arr, new_root).each { |e a << e }; end; end; end. Потом doit("purple", ["purp", "p", "ur", "le", "purpl"]) #=> [["purp", "le"], ["p", "ur", "p", "le"]].
Рекурсию можно было бы сделать намного более эффективной, сначала вычислив h = arr.repeated_permutation(2).with_object(Hash.new { |h,k| h[k] = [] }) { |(f,t),h| h[f] << t if word.include?([f,t].join) } #=> {"purp"=>["le"], "p"=>["ur", "le"], "ur"=>["p"]}. Это говорит нам, что если "purp" используется как часть слова, за ним может следовать только "le", если "p" используется как часть слова, за ним может следовать только "ur" или "le", и если "ur" используется как часть слова, он может следовать только "p".
Ответы 1
Вот способ сделать это:
def all_contruct target, wordBank
possibleWords = wordBank.select{|word| target.start_with? word}
possibleWords.each_with_object([]) do |word,result|
rest = target.delete_prefix word
if rest.empty?
result << [word]
else
send(__method__,rest,wordBank).each {|tail| result << [word] + tail}
end
end
end
all_contruct("purple",["purp","p","ur","le","purpl"])
#=> [["purp", "le"], ["p", "ur", "p", "le"]]
Обновлять: неожиданно оказалось однострочным
def all_contruct target, wordBank
wordBank.select{|w| target.start_with? w}.each_with_object([]) { |w,r| (t = target.delete_prefix w).empty? ? r << [w] : send(__method__,t,wordBank).each {|c| r << [w] + c} }
end
Спасибо за Ваш ответ. @fravadona
Пожалуйста ;-) Работает как надо?
Да, отлично, я, наверное, оптимизирую его с помощью Memoization.
Каков ваш ожидаемый результат?