Сделайте что-нибудь в середине рекурсивной функции, затем верните, если необходимо - PullRequest
Новая
       6

Сделайте что-нибудь в середине рекурсивной функции, затем верните, если необходимо

0 голосов
/ 31 января 2020

Как мне сделать что-то в середине рекурсии и вернуться по мере необходимости? Другими словами, может быть, больше нет необходимости в рекурсии, потому что я нашел «решение», и в этом случае для экономии ресурсов рекурсия может остановиться.

Например, допустим, у меня есть рабочий permute метод, который делает это 

permute([["a","b"],[1,2]])
>>> [["a", 1], ["a", 2], ["b", 1], ["b", 2]]

Вместо того, чтобы метод генерировал все 4 возможности, если один отвечает моим требованиям, я бы хотел, чтобы он прекратился. Например, допустим, я ищу ["a",2], затем метод может остановиться после создания второй возможности.

Это мой текущий permute метод, который работает 

def permute(arr)
  if arr.length == 1
    return arr.first
  else
    first = arr.shift
    return first.product(permute(arr)).uniq 
  end
end

Я чувствую, что мне нужно вставить блок do куда-нибудь, как показано ниже, но не уверен, как / где ... 

if result_of_permutation_currently == ["a",2]
   return ...
else
   # continuing the permutations
end

Ответы [ 2 ]

0 голосов
/ 02 февраля 2020

Вы можете написать свой метод следующим образом. 

def partial_product(arr, last_element)
  @a = []
  @last_element = last_element
  recurse(arr)
  @a
end


def recurse(arr, element = [])
  first, *rest = arr
  if rest.empty?
    first.each do |e|
      el = element + [e]
      @a << el
      return true if el == @last_element
    end
  else
    first.each do |e|
      rv = recurse(rest, element + [e])
      return true if rv
    end
  end
  false
end


arr = [["a","b"], [1,2,3], ["cat","dog"]]


partial_product(arr, ["b",2,"dog"])
  #=> [["a", 1, "cat"], ["a", 1, "dog"], ["a", 2, "cat"],
  #    ["a", 2, "dog"], ["a", 3, "cat"], ["a", 3, "dog"],
  #    ["b", 1, "cat"], ["b", 1, "dog"], ["b", 2, "cat"],
  #    ["b", 2, "dog"]]
partial_product(arr, ["a",1,"dog"])
  #=> [["a", 1, "cat"], ["a", 1, "dog"]] 
partial_product(arr, ["b",2,"pig"])
  #=> [["a", 1, "cat"], ["a", 1, "dog"], ["a", 2, "cat"],
  #    ["a", 2, "dog"], ["a", 3, "cat"], ["a", 3, "dog"],
  #    ["b", 1, "cat"], ["b", 1, "dog"], ["b", 2, "cat"],
  #    ["b", 2, "dog"], ["b", 3, "cat"], ["b", 3, "dog"]]

Если вы предпочитаете избегать использования переменных экземпляра, вы можете использовать a и last_element в качестве аргументов в recurse, но при этом будет неэффективно, особенно с точки зрения использования памяти.

0 голосов
/ 01 февраля 2020

Вот два способа, которые можно сделать без использования рекурсии.

Используйте each для генерации элементов нужного массива, пока не будет достигнута целевая пара 

def permute(arr1, arr2, last_pair = [])
  arr1.each_with_object([]) do |e1,a|
    arr2.each do |e2|
      a << [e1, e2]
      break a if [e1, e2] == last_pair
    end
  end
end


permute(["a","b"],[1,2],["b", 1])
  #=> [["a", 1], ["a", 2], ["b", 1]]
permute(["a","b"],[1,2],["b", 99])
  #=> [["a", 1], ["a", 2], ["b", 1], ["b", 2]] 
permute(["a","b"],[1,2])
  #=> [["a", 1], ["a", 2], ["b", 1], ["b", 2]] 
permute(["a","b"],[],["b", 1])
  #=> [] 
permute([],[1,2],["b", 1])
  #=> [] 
permute([],[],["b", 1])
  #=> []

Отображение последовательности индексов нужного массива 

def permute(arr1, arr2, last_pair = [])
  n1 = arr1.size
  n2 = arr2.size
  idx1 = arr1.index(last_pair.first)
  idx2 = idx1.nil? ? nil : arr2.index(last_pair.last)
  return arr1.product(arr2) if idx2.nil?
  0.step(to: idx1*n2+idx2).
    map {|i| [arr1[(i % (n1*n2))/n2], arr2[i % n2]]}
end


permute(["a","b"],[1,2],["b", 1])

См. Числовой # шаг

idx1*n2 + idx2, количество элементов в возвращаемом массиве вычисляется следующим образом. 

last_pair = ["b", 1]
n2 = arr2.size 
  #=> 2 
idx1 = arr1.index(last_pair.first)
  #=> 1 
idx2 = idx1.nil? ? nil : arr2.index(last_pair.last)      
    #=> 0 
  idx1*n2 + idx2
    #=> 2

Элемент с индексом i возвращаемого массива: 

n1 = arr1.size
  #=> 2
[arr1[(i % (n1*n2))/n2], arr2[i % n2]]
  #=> [["a","b"][(i % 2*2)/2], [1,2][i % 2]]

Для i = 1 это 

[["a","b"][(1 % 4)/2], [1,2][1 % 2]]
  #=> [["a","b"][0], [1,2][1]]
  #=> [“a”, 2]

Для i = 2 это 

[["a","b"][(2 % 4)/2], [1,2][2 % 2]]
  #=> [["a","b"][1], [1,2][0]]
  #=> [“b”,1]

Обратите внимание, что мы не можем написать 

arr1.lazy.product(arr2).first(idx1*n2+idx2+1)

, потому что arr1.lazy возвращает перечислитель (arr1.lazy #=> #<Enumerator::Lazy: ["a", "b"]>), но Array # product требует, чтобы его получатель был массив. По этой причине некоторые Rubyists хотели бы, чтобы product сделал метод Enumerable (с версией lazy), но не задерживайте дыхание.

...