How to determine if one array contains all elements of another array

Give开发者_StackOverflow中文版n:

a1 = [5, 1, 6, 14, 2, 8]

I would like to determine if it contains all elements of:

a2 = [2, 6, 15]

In this case the result is false.

Are there any built-in Ruby/Rails methods to identify such array inclusion?

One way to implement this is:

a2.index{ |x| !a1.include?(x) }.nil?

Is there a better, more readable, way?

a = [5, 1, 6, 14, 2, 8]
b = [2, 6, 15]

a - b
# => [5, 1, 14, 8]

b - a
# => [15]

(b - a).empty?
# => false

Perhaps this is easier to read:

a2.all? { |e| a1.include?(e) }

You can also use array intersection:

(a1 & a2).size == a1.size

Note that size is used here just for speed, you can also do (slower):

(a1 & a2) == a1

But I guess the first is more readable. These 3 are plain ruby (not rails).

This can be achieved by doing

(a2 & a1) == a2

This creates the intersection of both arrays, returning all elements from a2 which are also in a1. If the result is the same as a2, you can be sure you have all elements included in a1.

This approach only works if all elements in a2 are different from each other in the first place. If there are doubles, this approach fails. The one from Tempos still works then, so I wholeheartedly recommend his approach (also it's probably faster).

If there are are no duplicate elements or you don't care about them, then you can use the Set class:

a1 = Set.new [5, 1, 6, 14, 2, 8]
a2 = Set.new [2, 6, 15]
a1.subset?(a2)
=> false

Behind the scenes this uses

all? { |o| set.include?(o) }

You can monkey-patch the Array class:

class Array
    def contains_all?(ary)
        ary.uniq.all? { |x| count(x) >= ary.count(x) }
    end
end

test

irb(main):131:0> %w[a b c c].contains_all? %w[a b c]
=> true
irb(main):132:0> %w[a b c c].contains_all? %w[a b c c]
=> true
irb(main):133:0> %w[a b c c].contains_all? %w[a b c c c]
=> false
irb(main):134:0> %w[a b c c].contains_all? %w[a]
=> true
irb(main):135:0> %w[a b c c].contains_all? %w[x]
=> false
irb(main):136:0> %w[a b c c].contains_all? %w[]
=> true
irb(main):137:0> %w[a b c d].contains_all? %w[d c h]
=> false
irb(main):138:0> %w[a b c d].contains_all? %w[d b c]
=> true

Of course the method can be written as a standard-alone method, eg

def contains_all?(a,b)
    b.uniq.all? { |x| a.count(x) >= b.count(x) }
end

and you can invoke it like

contains_all?(%w[a b c c], %w[c c c])

Indeed, after profiling, the following version is much faster, and the code is shorter.

def contains_all?(a,b)
    b.all? { |x| a.count(x) >= b.count(x) }
end

Most answers based on (a1 - a2) or (a1 & a2) would not work if there are duplicate elements in either array. I arrived here looking for a way to see if all letters of a word (split to an array) were part of a set of letters (for scrabble for example). None of these answers worked, but this one does:

def contains_all?(a1, a2)
  try = a1.chars.all? do |letter|
    a1.count(letter) <= a2.count(letter)
  end
  return try
end

Depending on how big your arrays are you might consider an efficient algorithm O(n log n)

def equal_a(a1, a2)
  a1sorted = a1.sort
  a2sorted = a2.sort
  return false if a1.length != a2.length
  0.upto(a1.length - 1) do 
    |i| return false if a1sorted[i] != a2sorted[i]
  end
end

Sorting costs O(n log n) and checking each pair costs O(n) thus this algorithm is O(n log n). The other algorithms cannot be faster (asymptotically) using unsorted arrays.

I was directed to this post when trying to find whether one array ["a", "b", "c"] contained another array ["a", "b"], where in my case identical ordering was an additional requirement to the question.

Here is my solution (I believe it's O(n) complexity), to anyone who has that extra requirement:

def array_includes_array(array_to_inspect, array_to_search_for)
  inspectLength = array_to_inspect.length
  searchLength = array_to_search_for.length

  if searchLength == 0 then
    return true
  end

  if searchLength > inspectLength then
    return false
  end

  buffer = []

  for i in 0..inspectLength
    buffer.push(array_to_inspect[i])

    bufferLastIndex = buffer.length - 1
    if(buffer[bufferLastIndex] != array_to_search_for[bufferLastIndex]) then
      buffer.clear
      next
    end

    if(buffer.length == searchLength) then
      return true
    end
  end

  return false
end

This produces the test results:

puts "1: #{array_includes_array(["a", "b", "c"], ["b", "c"])}" # true
puts "2: #{array_includes_array(["a", "b", "c"], ["a", "b"])}" # true
puts "3: #{array_includes_array(["a", "b", "c"], ["b", "b"])}" # false
puts "4: #{array_includes_array(["a", "b", "c"], ["c", "b", "a"])}" # false
puts "5: #{array_includes_array(["a", "b", "c"], [])}" # true
puts "6: #{array_includes_array([], ["a"])}" # false
puts "7: #{array_includes_array([], [])}" # true