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

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

您的代码包含两个错误，其中一个导致错误消息。

(0..words.length)循环从0到6。然而，words[6]并不存在(数组是基于零的)，所以您可以得到零。用(0..words.length-1)代替(两次)应该能解决这个问题。

您将获得每一个正确的结果两次，一次作为"action europe"，一次作为"europe action"。这是由于循环过多造成的，每个组合重复两次。将第二个循环从(0..words.length-1)替换为(i..words.length-1)。

索引的这种繁琐的记账方式令人厌烦，经常导致错误。这就是为什么Ruby程序员通常更喜欢更无麻烦的方法(就像其他答案中的combination一样)，完全避免索引。

Answer 2

下面的代码旨在提供一种高效的方法，在字数较大时构造所需的数组。注意，与其他答案不同，它没有使用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)的元素数组，这些元素包含键给出的元音，而不是其他的元音。因此，这些值共同构成了words的分区。当字数很大时，人们会期望h有31个键(2**5 - 1)。

现在我们循环遍历h的键值对。对于每一个，使用键k和值v，确定缺失元音集(vowels_needed)，然后循环遍历h的键-值对[kk, vv] ( 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。

各个变量由阵列分解赋值。

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

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

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的果树基准代码的方法进行了比较。唯一的区别是要测试的单词数组和将我的方法添加到基准测试中，我将其命名为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对随机选择的1000个单词。这个数组包含125,068对包含所有五个元音的单词。结果如下：

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

为了了解基准测试的可变性，我又进行了两次比较，每一次都随机选择了1000个单词。这给了我以下结果：

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

可见，样品之间存在着较大的差异。

Answer 3

你说的是对，所以我假设它是两个元素的组合。我使用#combination方法对数组中的每个元素进行了组合。然后，我#select，-ed，只包含所有元音的对，一旦它们被加入。最后，我确保加入这两对：

["goat", "action", "tear", "impromptu", "tired", "europe"]
.combination(2)
.select { |c| c.join('') =~ /\b(?=\w*?a)(?=\w*?e)(?=\w*?i)(?=\w*?o)(?=\w*?u)[a-zA-Z]+\b/ }
.map{ |w| w.join(' ') }

#=> ["action europe", "tear impromptu"]

正则表达式来自"与包含所有元音的单词匹配的正则表达式是什么？“。