Heavy load on the computer caused by repeated permutations

Question

I'm having the following problem, I want to make every possible combination in an array of strings, and return only a specific combination of elements within the total amount of combinations.

The array looks something like this.

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

In this example, the input would be

source = 'a'   target = 'd'

And the code that I'm using right now to get the string I want is this.

(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

The output would look something like this

['abbd']

What I want to make sure when I select the strings, is that the last letter of a string is the first one of the next.

Right now it works, but I'm encountering several issues,

1. With huge repeated permutations, 8 or above, the computer just freezes, it is unable to handle such a huge amount of combinations, so I need a different approach to reduce the load.

2. It is difficult to implement a selection procedure prior to the permutations to help reduce the load as it is after the repeated_permutations method is executed that the combinations are generated.

Answer 1

I.

You can see that it is at first just an Enumerator (that never freezes your computer until you cast it to Array or iterate through it):

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

And the .map converts is to Array. To avoid it you should either use the lazy block form:

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

or better call .find on it, so it would return nil (that works like a false in condition statements) if can't find some:

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

II.

I guess you want to find the path from one verticle to another in a graph.
I believe this was implemented in Ruby here a lot of times and you may have a look at the "Optimizing breadth-first-search code" question on Codereview site