ruby - 如何找到包含所有元音的同一数组的两个元素

Question

我想迭代给定的数组，例如:

["goat", "action", "tear", "impromptu", "tired", "europe"]

我想查看所有可能的配对。

所需的输出是一个新数组，其中包含所有对，组合包含所有元音。此外，这些对应该连接为输出数组的一个元素:

["action europe", "tear impromptu"]

我尝试了以下代码，但收到一条错误消息:

No implicit conversion of nil into string.

def all_vowel_pairs(words)
  pairs = []

  (0..words.length).each do |i|                       # iterate through words
    (0..words.length).each do |j|                   # for every word, iterate through words again
      pot_pair = words[i].to_s + words[j]         # build string from pair
      if check_for_vowels(pot_pair)               # throw string to helper-method.
        pairs << words[i] + " " + words[j]      # if gets back true, concatenade and push to output array "pairs"
      end
    end
  end
  pairs
end

# helper-method to check for if a string has all vowels in it
def check_for_vowels(string)
  vowels = "aeiou"
  founds = []
  string.each_char do |char|
    if vowels.include?(char) && !founds.include?(char)
      founds << char
    end
  end
  if founds.length == 5
    return true
  end
  false
end

Answer 1

以下代码旨在提供一种在字数很大时构建所需数组的有效方法。请注意，与其他答案不同，它不使用方法 Array#combination .
说明部分的第一部分(下文)概述了算法采用的方法。然后填写详细信息。
代码

require 'set'

VOWELS = ["a", "e", "i", "o", "u"]
VOWELS_SET = VOWELS.to_set

def all_vowel_pairs(words)
  h = words.each_with_object({}) {|w,h| (h[(w.chars & VOWELS).to_set] ||= []) << w}
  h.each_with_object([]) do |(k,v),a|
    vowels_needed = VOWELS_SET-k
    h.each do |kk,vv|
      next unless kk.superset?(vowels_needed)
      v.each {|w1| vv.each {|w2| a << "%s %s" % [w1, w2] if w1 < w2}}
    end
  end
end

示例

words = ["goat", "action", "tear", "impromptu", "tired", "europe", "hear"]

all_vowel_pairs(words)
  #=> ["action europe", "hear impromptu", "impromptu tear"]

说明
对于给定的示例，步骤如下。

VOWELS_SET = VOWELS.to_set
  #=> #<Set: {"a", "e", "i", "o", "u"}> 

h = words.each_with_object({}) {|w,h| (h[(w.chars & VOWELS).to_set] ||= []) << w}
  #=> {#<Set: {"o", "a"}>=>["goat"],
  #    #<Set: {"a", "i", "o"}>=>["action"],
  #    #<Set: {"e", "a"}>=>["tear", "hear"],
  #    #<Set: {"i", "o", "u"}>=>["impromptu"],
  #    #<Set: {"i", "e"}>=>["tired"],
  #    #<Set: {"e", "u", "o"}>=>["europe"]}

可以看出 h的键是五个元音的子集。这些值是 words 的元素数组(词)包含由键给出的元音，没有其他元音。因此，这些值共同构成了 words 的分区。 .当单词数很大时，我们会期望 h有 31 个键( 2**5 - 1 )。
我们现在遍历 h 的键值对.对于每个，用 key k和值(value) v ，确定缺失元音集( vowels_needed )，然后我们循环遍历这些键值对 [kk, vv]的 h其中 kk是 vowels_needed 的超集. v的所有元素组合和 vv然后将它们添加到要返回的数组中(经过调整以避免重复计算每对单词)。
继续，

enum = h.each_with_object([])
  #=> #<Enumerator: {#<Set: {"o", "a"}>=>["goat"],
  #                  #<Set: {"a", "i", "o"}>=>["action"],
  #                  ...
  #                  #<Set: {"e", "u", "o"}>=>["europe"]}: 
  #     each_with_object([])> 

第一个值由 enum 生成并传递给块，块变量被赋值:

(k,v), a = enum.next
  #=> [[#<Set: {"o", "a"}>, ["goat"]], []]

见 Enumerator#next .
单个变量由 array decomposition 赋值:

k #=> #<Set: {"o", "a"}> 
v #=> ["goat"] 
a #=> [] 

现在执行块计算。

vowels_needed = VOWELS_SET-k
  #=> #<Set: {"e", "i", "u"}> 
h.each do |kk,vv|
  next unless kk.superset?(vowels_needed)
  v.each {|w1| vv.each {|w2| a << "%s %s" % [w1, w2] if w1 < w2}}
end

单词“goat”( v )具有元音“o”和“a”，因此它只能与包含元音“e”、“i”和“u”(可能还有“o”和/)的词匹配或“一个”)。表达方式

next unless kk.superset?(vowels_needed)

跳过 h 的那些键( kk ) 不是 vowels_needed 的超集.见 Set#superset? . words中的词都没有包含“e”、“i”和“u”，所以数组 a不变。
下一个元素现在由 enum 生成, 传递给块，块变量被赋值:

(k,v), a = enum.next
  #=> [[#<Set: {"a", "i", "o"}>, ["action"]], []] 
k #=> #<Set: {"a", "i", "o"}> 
v #=> ["action"] 
a #=> [] 

块计算开始:

vowels_needed = VOWELS_SET-k
  #=> #<Set: {"e", "u"}> 

我们看到 h只有一个键值对，其键是 vowels_needed 的超集:

kk = %w|e u o|.to_set
  #=> #<Set: {"e", "u", "o"}> 
vv = ["europe"]

因此我们执行:

v.each {|w1| vv.each {|w2| a << "%s %s" % [w1, w2] if w1 < w2}}

将一个元素添加到 a :

a #=> ["action europe"]

条款 if w1 < w2是为了确保后面的计算 "europe action"未添加到 a .
如 v (包含“a”、“i”和“u”的词)和 vv (包含“e”、“u”和“o”的词)改为:

v  #=> ["action", "notification"]
vv #=> ["europe", "route"]

我们会添加 "action europe" , "action route"和 "notification route"至 a . ( ”europe notification” 将在稍后添加，当 k #=> #<Set: {"e", "u", "o"} 时。)
基准
我使用@theTinMan 的 Fruity 基准代码将我的方法与其他人建议的方法进行了基准测试。唯一的区别在于要测试的单词数组以及将我的方法添加到基准测试中，我将其命名为 cary .对于要考虑的单词数组，我从计算机上的英语单词文件中随机选择了 600 个单词:

words = IO.readlines('/usr/share/dict/words', chomp: true).sample(600)
words.first 10
  #=> ["posadaship", "explosively", "expensilation", "conservatively", "plaiting",
  #    "unpillared", "intertwinement", "nonsolidified", "uraemic", "underspend"]

发现该数组包含 46,436 对包含所有五个元音的单词。
结果如下所示。

compare {
  _viktor { viktor(words) }
  _ttm1 { ttm1(words) }
  _ttm2 { ttm2(words) }
  _ttm3 { ttm3(words) }
  _cary { cary(words) }
}

Running each test once. Test will take about 44 seconds.
_cary is faster than _ttm3 by 5x ± 0.1
_ttm3 is faster than _viktor by 50.0% ± 1.0%
_viktor is faster than _ttm2 by 30.000000000000004% ± 1.0%
_ttm2 is faster than _ttm1 by 2.4x ± 0.1

然后我比较了 cary与 ttm3对于 1,000 个随机选择的单词。发现该数组包含 125,068 对包含所有五个元音的单词。结果如下:

Running each test once. Test will take about 19 seconds.
_cary is faster than _ttm3 by 3x ± 1.0

为了感受基准测试的可变性，我又进行了两次最后的比较，每次都随机选择了 1,000 个单词。这给了我以下结果:

Running each test once. Test will take about 17 seconds.
_cary is faster than _ttm3 by 5x ± 1.0

Running each test once. Test will take about 18 seconds.
_cary is faster than _ttm3 by 4x ± 1.0

可以看出，样本之间存在相当大的差异。