Большая нагрузка на компьютер, вызванная многократными перестановками

Question

У меня возникла следующая проблема: я хочу сделать каждую возможную комбинацию в массиве строк и вернуть только определенную комбинацию элементов в общем количестве комбинаций.

Массив выглядит примерно так.

array = ['ab','bc','cd','de','bd','ae']

В этом примере вход будет

source = 'a'   target = 'd'

И код, который я использую сейчас, чтобы получить строку, которую я хочу, это.

(2..2).flat_map do |n|
  array.repeated_permutation(n).map(&:join).select do |string|
    string[0] == source && string[-1] == target && string[1..2].squeeze.size == n - 1
  end
end

Вывод будет выглядеть примерно так

['abbd']

Когда я выбираю строки, я хочу убедиться, что последняя буква строки является первой из следующих.

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

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

2. Трудно реализовать процедуру выбора до перестановок, чтобы помочь уменьшить нагрузку, поскольку именно после того, как выполняется метод repeat_permutations, генерируются комбинации.

Answer 1

Я.

Вы можете видеть, что сначала это просто Enumerator (который никогда не замораживает ваш компьютер, пока вы не преобразуете его в Array или не выполняете его итерацию):

array.repeated_permutation(2)
=> #<Enumerator: ["ab", "bc", "cd", "de", "bd", "ae"]:repeated_permutation(2)>

И .map преобразует в массив. Чтобы избежать этого, вы должны использовать форму ленивых блоков:

array.repeated_permutation(2) do |a, b|
  break [a, b].join if a[0] == source && a[-1] == b[0] && b[1] == target
end

или лучше позвонить .find на это, так что вернется nil (это работает как false в условии условия), если не может найти некоторые:

array.repeated_permutation(2).find do |a, b|
  a[0] == source && a[-1] == b[0] && b[1] == target
end

II.

Я думаю, вы хотите найти путь от одной вертикали к другому на графике.
Я полагаю, что это было реализовано в Ruby здесь много раз, и вы можете посмотреть на вопрос "Оптимизация кода поиска в начале" на сайте Codereview.