在 Ruby 的数组中查找与特定条件匹配的所有组合

Question

我有以下数组：

a = ["melon | apple", "kiwi | melon", "apple | orange", "pineapple | kiwi"]

我希望通过连接字符串元素的后半部分("|"之后(和以下字符串元素的前一部分("|"之前(来生成所有字符串。a.combination_with_criteria(3).to_a应输出：

["kiwi | melon", "melon | apple", "apple | orange"]
["pineapple | kiwi", "kiwi | melon", "melon | apple"]

a.combination(3).to_a给出了所有可能的组合，但顺序是随机的。

也许为此目的使用哈希值会更好。

Answer 1

这似乎有效：

def find_chains(input)
# Split input into usable value pairs.
pairs = input.map { |s| s.split(" | ") }
pairs.permutation(3).select do |ar|
ar[0][1] == ar[1][0] && ar[1][1] == ar[2][0]
end
end
input = ["melon | apple", "kiwi | melon", "apple | orange", "pineapple | kiwi"]
find_chains(input).each do |match|
puts "match: " + match.map { |ar| ar.join(" | ")}.join(", ")
end
# Output:
#
# match: kiwi | melon, melon | apple, apple | orange
# match: pineapple | kiwi, kiwi | melon, melon | apple

Answer 2

a.combination(3).to_a给出了所有可能的组合，但顺序是随机的。

我看看：

a.combination(3).to_a
#=> [
#     ["melon | apple", "kiwi | melon", "apple | orange"],
#     ["melon | apple", "kiwi | melon", "pineapple | kiwi"],
#     ["melon | apple", "apple | orange", "pineapple | kiwi"],
#     ["kiwi | melon", "apple | orange", "pineapple | kiwi"]
#   ]

显然，它既不包含["kiwi | melon", "melon | apple", "apple | orange"]，也不包含["pineapple | kiwi", "kiwi | melon", "melon | apple"].

要获得这些，您必须改用permutation：

a.permutation(3).to_a
#=> [
#     ["melon | apple", "kiwi | melon", "apple | orange"],
#     ["melon | apple", "kiwi | melon", "pineapple | kiwi"],
#     ["melon | apple", "apple | orange", "kiwi | melon"],
#     ["melon | apple", "apple | orange", "pineapple | kiwi"],
#     ["melon | apple", "pineapple | kiwi", "kiwi | melon"],
#     ["melon | apple", "pineapple | kiwi", "apple | orange"],
#     ["kiwi | melon", "melon | apple", "apple | orange"],      <--- here
#     ["kiwi | melon", "melon | apple", "pineapple | kiwi"],
#     ["kiwi | melon", "apple | orange", "melon | apple"],
#     ["kiwi | melon", "apple | orange", "pineapple | kiwi"],
#     ["kiwi | melon", "pineapple | kiwi", "melon | apple"],
#     ["kiwi | melon", "pineapple | kiwi", "apple | orange"],
#     ["apple | orange", "melon | apple", "kiwi | melon"],
#     ["apple | orange", "melon | apple", "pineapple | kiwi"],
#     ["apple | orange", "kiwi | melon", "melon | apple"],
#     ["apple | orange", "kiwi | melon", "pineapple | kiwi"],
#     ["apple | orange", "pineapple | kiwi", "melon | apple"],
#     ["apple | orange", "pineapple | kiwi", "kiwi | melon"],
#     ["pineapple | kiwi", "melon | apple", "kiwi | melon"],
#     ["pineapple | kiwi", "melon | apple", "apple | orange"],
#     ["pineapple | kiwi", "kiwi | melon", "melon | apple"],    <--- here
#     ["pineapple | kiwi", "kiwi | melon", "apple | orange"],
#     ["pineapple | kiwi", "apple | orange", "melon | apple"],
#     ["pineapple | kiwi", "apple | orange", "kiwi | melon"]
#   ]

您可能知道select可以用来过滤掉正确的元素，但条件是什么样的？

让我们取一对匹配的配对：

a = 'kiwi | melon'
b = 'melon | apple'

我们可以通过' | '来split这些零件：

a.split(' | ') #=> ["kiwi", "melon"]
b.split(' | ') #=> ["melon", "apple"]

如果a的最后一个单词与b的第一个单词匹配，则匹配：

a.split(' | ').last == b.split(' | ').first
#=> true

要检查数组中每对连续字符串的这一点，我们可以使用each_cons：

['kiwi | melon', 'melon | apple', 'apple | orange'].each_cons(2) do |a, b|
p a.split(' | ').last == b.split(' | ').first
end

它首先传递'kiwi | melon'并'melon | apple'到块，然后'melon | apple'并'apple | orange'。

对于此数组，输出为：

true
true

要确定块是否为所有货币对返回true，我们可以将all?附加到each_cons：

['kiwi | melon', 'melon | apple', 'apple | orange'].each_cons(2).all? do |a, b|
a.split(' | ').last == b.split(' | ').first
end

这正是我们可以传递给select的：

a.permutation(3).select do |sub_array|
sub_array.each_cons(2).all? do |a, b|
a.split(' | ').last == b.split(' | ').first
end
end
#=> [
#     ["kiwi | melon", "melon | apple", "apple | orange"],
#     ["pineapple | kiwi", "kiwi | melon", "melon | apple"]
#   ]

请注意，这仍然会创建一个包含所有排列的巨大临时数组，并且它会为每个比较拆分字符串，因此您可能需要寻找更优化的解决方案。但这应该让你开始。