Determine if one array contains all elements of another array

Question

I need to tell if an array contains all of the elements of another array with duplicates.

[1,2,3].contains_all? [1,2] #=> true
[1,2,3].contains_all? [1,2,2] #=> false (this is where (a1-a2).empty? fails)
[2,1,2,3].contains_all? [1,2,2] #=> true

So the first array must contain as many or equal of the number of each unique element in the second array.

This question answers it for those using an array as a set, but I need to control for duplicates.

Update: Benchmarks

On Ruby 1.9.3p194

def bench
 puts Benchmark.measure {
 10000.times do
 [1,2,3].contains_all? [1,2]
 [1,2,3].contains_all? [1,2,2]
 [2,1,2,3].contains_all? [1,2,2]
 end
 }
end

Results in:

Rohit 0.100000 0.000000 0.100000 ( 0.104486)
Chris 0.040000 0.000000 0.040000 ( 0.040178)
Sergio 0.160000 0.020000 0.180000 ( 0.173940)
sawa 0.030000 0.000000 0.030000 ( 0.032393)

Update 2: Larger Arrays

@a1 = (1..10000).to_a
@a2 = (1..1000).to_a
@a3 = (1..2000).to_a
def bench
 puts Benchmark.measure {
 1000.times do
 @a1.contains_all? @a2
 @a1.contains_all? @a3
 @a3.contains_all? @a2
 end
 }
end

Results in:

Rohit 9.750000 0.410000 10.160000 ( 10.158182)
Chris 10.250000 0.180000 10.430000 ( 10.433797)
Sergio 14.570000 0.070000 14.640000 ( 14.637870)
sawa 3.460000 0.020000 3.480000 ( 3.475513)

• rohit89: You should benchmark for much bigger arrays. (Unless its always going to be small for your use-case)
• Chris: looks like @sawa's answer definitely wins for huge arrays, but I'm never going to have arrays that large. Regardless, sawa's implementation seems to be the best so far
• rohit89: If you flip it, like @a2.contains_all? @a1, the hash based answers will be faster. Though for small arrays, it really doesn't matter which way you go.
• Chris: You would probably add a check to make sure the other array is smaller (impossible to return true) so that scenario would be constant time for all.

Answer 1

class Array
 def contains_all? other
 other = other.dup
 each{|e| if i = other.index(e) then other.delete_at(i) end}
 other.empty?
 end
end

• Chris: nice! Seems like the best so far

Answer 2

Here's a naive and straightforward implementation (not the most efficient one, likely). Just count the elements and compare both elements and their occurrence counts.

class Array
 def contains_all? ary
 # group the arrays, so that 
 # [2, 1, 1, 3] becomes {1 => 2, 2 => 1, 3 => 1}
 my_groups = group_and_count self
 their_groups = group_and_count ary
 their_groups.each do |el, cnt|
 if !my_groups[el] || my_groups[el] < cnt
 return false
 end
 end
 true
 end
 private
 def group_and_count ary
 ary.reduce({}) do |memo, el|
 memo[el] ||= 0
 memo[el] += 1
 memo
 end
 end
end
[1, 2, 3].contains_all? [1, 2] # => true
[1, 2, 3].contains_all? [1, 2, 2] # => false
[2, 1, 2, 3].contains_all? [1, 2, 2] # => true
[1, 2, 3].contains_all? [] # => true
[].contains_all? [1, 2] # => false

Answer 3

It seems you need a multiset. Check out this gem, I think it does what you need.

You can use is and do something like (if the intersection is equal to the second multiset then the first one includes all of its elements):

@ms1 & @ms2 == @ms2

Answer 4

Counting the number of occurrences and comparing them seems to be the obvious way to go.

class Array
 def contains_all? arr
 h = self.inject(Hash.new(0)) {|h, i| h[i] += 1; h}
 arr.each do |i|
 return false unless h.has_key?(i)
 return false if h[i] == 0
 h[i] -= 1
 end
 true
 end
end

• sawa: If you are caring about speed, changing == 0 to zero? will slightly improve the speed.

Answer 5

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

The following version is faster and shorter in code.

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

Answer 6

Answering with my own implementation, but definitely want to see if someone can come up with a more efficient way. (I won't accept my own answer)

class Array
 def contains_all?(a2)
 a2.inject(self.dup) do |copy, el|
 if copy.include? el
 index = copy.index el
 copy.delete_at index
 else
 return false
 end
 copy
 end
 true
 end
end

And the tests:

1.9.3p194 :016 > [1,2,3].contains_all? [1,2] #=> true
 => true 
1.9.3p194 :017 > [1,2,3].contains_all? [1,2,2] #=> false (this is where (a1-a2).empty? fails)
 => false 
1.9.3p194 :018 > [2,1,2,3].contains_all? [1,2,2] #=> true
 => true 

• rohit89: AFAIK Array#index and Array#include? are O(n). The array is iterated for each call. So if you have large arrays, that could pose a problem. And you can break out of the loop when contains = false.

Answer 7

This solution will only iterate through both lists once, and hence run in linear time. It might however be too much overhead if the lists are expected to be very small.

 class Array
 def contains_all?(other)
 return false if other.size > size
 elem_counts = other.each_with_object(Hash.new(0)) { |elem,hash| hash[elem] += 1 }
 each do |elem|
 elem_counts.delete(elem) if (elem_counts[elem] -= 1) <= 0
 return true if elem_counts.empty?
 end
 false
 end
 end

Answer 8

If you can't find a method, you can build one using ruby's include? method.

Official documentation: http://www.ruby-doc.org/core-1.9.3/Array.html#method-i-include-3F

Usage:

array = [1, 2, 3, 4]
array.include? 3 #=> true

Then, you can do a loop:

def array_includes_all?( array, comparision_array )
 contains = true
 for i in comparision_array do
 unless array.include? i
 contains = false
 end
 end
 return contains
end
array_includes_all?( [1,2,3,2], [1,2,2] ) #=> true

• Chris: but array_includes_all?( [1,2,3], [1,2,2,2] ) will also be true because include?(2) will keep finding the same 2
• Sergio Tulentsev: Your code fails on OP's second example. It returns true, when it should return false.
• macool: I'm sorry, I think I misunderstood the question.