CODEWITHSUNDEEP
ruby
Tao
Tao

Reputation: 990

How to determine whether an array is contained in another array

The question is, given [1,2,3,4,5] and [2,4,5], to determine whether (every element in) the second array is contained in the first one. The answer is true.

What's the most succinct and efficient way to do better than:

arr2.reject { |e| arr1.include?(e) } .empty?

Upvotes: 0

Views: 98

Answers (3)

Sagar Pandya
Sagar Pandya

Reputation: 9497

As mentioned by @Ryan you can use sets. In which case Set#subset? is available to you which is pretty readable (note the two different ways of defining a set from an array):

require 'set'

s1 = Set.new([1, 2, 3])
s2 = [1, 2].to_set
s3 = [1, 3].to_set
s4 = [1, 4].to_set

s1.subset? s1 #=> true
s2.subset? s1 #=> true
s3.subset? s1 #=> true
s4.subset? s1 #=> false

Also consider using Set#proper_subset if required.

s1.proper_subset? s1 #=> false
s2.proper_subset? s1 #=> true

NB A set contains no duplicate elements e.g. Set.new([1,2,3,3]) #=> #<Set: {1, 2, 3}>

Upvotes: 1

Max
Max

Reputation: 1957

Array subtraction should work, as in

(arr2 - arr1).empty?

Description of method:

Returns a new array that is a copy of the original array, removing any items that also appear in [the second array]. The order is preserved from the original array.

It compares elements using their hash and eql? methods for efficiency.

I don't consider myself an expert on efficiency, but @Ryan indicated in comments to his answer that it's reasonably efficient at scale.

Upvotes: 4

Ry-
Ry-

Reputation: 224857

The bad O(n²) one-liner would look like this:

arr2.all? { |x| arr1.include? x }
arr2.all? &arr1.method(:include?)  # alternative

If your objects are hashable, you can make this O(n) by making a set out of the first array:

require 'set'

arr2.all? &Set.new(arr1).method(:include?)

If your objects are totally, like, ordered, you can make it O(n log n) with a sort and a binary search:

arr1.sort!
arr2.all? { |x| arr1.bsearch { |y| x <=> y } }

Upvotes: 3

Related Questions