How to find two elements of the same array that contain all vowels

Question

I want to iterate a given array, for example:

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

I want to look at all possible pairs.

The desired output is a new array, which contains all pairs, that combined contain all vowels. Also those pairs should be concatenated as one element of the output array:

["action europe", "tear impromptu"]

I tried the following code, but got an error message:

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

The following code is intended to provide an efficient way to construct the desired array when the number of words is large. Note that, unlike the other answers, it does not make use of the method Array#combination.

The first part of the section Explanation (below) provides an overview of the approach taken by the algorithm. The details are then filled in.

Code

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

Example

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

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

Explanation

For the given example the steps are as follows.

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"]}

It is seen that the keys of h are subsets of the five vowels. The values are arrays of elements of words (words) that contain the vowels given by the key and no others. The values therefore collectively form a partition of words. When the number of words is large one would expect h to have 31 keys (2**5 - 1).

We now loop through the key-value pairs of h. For each, with key k and value v, the set of missing vowels (vowels_needed) is determined, then we loop through those keys-value pairs [kk, vv] of h for which kk is a superset of vowels_needed. All combinations of elements of v and vv are then added to the array being returned (after an adjustment to avoid double-counting each pair of words).

Continuing,

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

The first value is generated by enum and passed to the block, and the block variables are assigned values:

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

See Enumerator#next.

The individual variables are assigned values by array decomposition:

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

The block calculations are now performed.

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

The word "goat" (v) has vowels "o" and "a", so it can only be matched with words that contain vowels "e", "i" and "u" (and possibly "o" and/or "a"). The expression

next unless kk.superset?(vowels_needed)

skips those keys of h (kk) that are not supersets of vowels_needed. See Set#superset?.

None of the words in words contain "e", "i" and "u" so the array a is unchanged.

The next element is now generated by enum, passed to the block and the block variables are assigned values:

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

The block calculation begins:

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

We see that h has only one key-value pair for which the key is a superset of vowels_needed:

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

We therefore execute:

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

which adds one element to a:

a #=> ["action europe"]

The clause if w1 < w2 is to ensure that later in the calculations "europe action" is not added to a.

If v (words containing 'a', 'i' and 'u') and vv (words containing 'e', 'u' and 'o') had instead been:

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

we would have added "action europe", "action route" and "notification route" to a. (”europe notification” would be added later, when k #=> #<Set: {"e", "u", "o"}.)

Benchmark

I benchmarked my method against others suggested using @theTinMan's Fruity benchmark code. The only differences were in the array of words to be tested and the addition of my method to the benchmark, which I named cary. For the array of words to be considered I selected 600 words at random from a file of English words on my computer:

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

This array was found to contain 46,436 pairs of words containing all five vowels.

The results were as shown below.

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

I then compared cary with ttm3 for 1,000 randomly selected words. This array was found to contain 125,068 pairs of words containing all five vowels. That result was as follows:

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

To get a feel for the variability of the benchmark I ran this last comparison twice more, each with a new random selection of 1,000 words. That gave me the following results:

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

It is seen the there is considerable variation among the samples.

Answer 2

You said pairs so I assume it's a combination of two elements. I've made a combination of each two elements in the array using the #combination method. Then I #select-ed only those pairs that contain all vowels once they're joined. Finally, I made sure to join those pairs :

["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"]

The regex is from "What is the regex to match the words containing all the vowels?".