重复排列导致电脑负载过重

Question

我遇到了以下问题，我想在一个字符串数组中进行所有可能的组合，并且return只有组合总数中的特定元素组合。

数组看起来像这样。

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']

当我 select 字符串时，我想确定的是字符串的最后一个字母是下一个字母的第一个。

现在可以用了，但是我遇到了几个问题，

大量的重复排列，8个或以上，电脑死机，无法处理如此庞大的组合，所以我需要一个不同的方法来减少负载。
很难在排列之前实施 selection 过程以帮助减少负载，因为在执行 repeated_permutations 方法之后生成组合.

Answer 1

我.

您可以看到它起初只是一个枚举器（它永远不会冻结您的计算机，直到您将它转换为数组或遍历它）：

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，所以它会 return nil （在条件语句中类似于 false）如果找不到：

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

二.

我猜你想在图中找到从一个顶点到另一个顶点的路径。
我相信这已在 Ruby 中实施了很多次，您可以查看 "Optimizing breadth-first-search code" question on Codereview site

重复排列导致电脑负载过重

Heavy load on the computer caused by repeated permutations

ruby

arrays

performance

permutation

memory-efficient

我.

二.