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)

You should benchmark for much bigger arrays. (Unless its always going to be small for your use-case) — rohit89
– rohit89, Commented Nov 25, 2012 at 18:53
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 — Chris
– Chris, Commented Nov 25, 2012 at 19:02
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. — rohit89
– rohit89, Commented Nov 25, 2012 at 19:08
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. — Chris
– Chris, Commented Nov 25, 2012 at 19:14

sawa · Accepted Answer · 2012-11-25 18:44:30Z

7

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

answered Nov 25, 2012 at 18:44

sawa

169k51 gold badges287 silver badges398 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Chris Over a year ago

nice! Seems like the best so far

Sergio Tulentsev · Accepted Answer · 2012-11-25 18:21:31Z

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

davidrac · Accepted Answer · 2012-11-25 18:44:34Z

2

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

answered Nov 25, 2012 at 18:44

davidrac

10.8k3 gold badges45 silver badges71 bronze badges

Comments

rohit89 · Accepted Answer · 2012-11-25 18:25:04Z

1

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

answered Nov 25, 2012 at 18:25

rohit89

5,7833 gold badges28 silver badges42 bronze badges

1 Comment

sawa Over a year ago

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

Jon Snow · Accepted Answer · 2017-09-15 16:32:17Z

1

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

edited Sep 15, 2017 at 16:32

answered Sep 15, 2017 at 15:54

Jon Snow

12k9 gold badges74 silver badges82 bronze badges

Comments

Chris · Accepted Answer · 2012-11-25 18:41:34Z

0

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

edited Nov 25, 2012 at 18:41

answered Nov 25, 2012 at 18:30

Chris

12.3k19 gold badges95 silver badges151 bronze badges

1 Comment

rohit89 Over a year ago

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.

Joel · Accepted Answer · 2012-11-26 08:32:34Z

0

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

answered Nov 26, 2012 at 8:32

Joel

1231 silver badge4 bronze badges

Comments

macool · Accepted Answer · 2012-11-25 18:16:03Z

-1

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

answered Nov 25, 2012 at 18:16

macool

6586 silver badges11 bronze badges

3 Comments

Chris Over a year ago

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 Over a year ago

Your code fails on OP's second example. It returns true, when it should return false.

macool Over a year ago

I'm sorry, I think I misunderstood the question.

Collectives™ on Stack Overflow

Determine if one array contains all elements of another array

Update: Benchmarks

Update 2: Larger Arrays

8 Answers 8

1 Comment

Comments

Comments

1 Comment

Comments

1 Comment

Comments

3 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

Update: Benchmarks

Update 2: Larger Arrays

8 Answers 8

1 Comment

Comments

Comments

1 Comment

Comments

1 Comment

Comments

3 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related