CODEWITHSUNDEEP
ruby-on-railsarraysruby
Misha Moroshko
Misha Moroshko

Reputation: 171489

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

Given:

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?

Upvotes: 222

Views: 146881

Answers (9)

Mario Pérez Alarcón
Mario Pérez Alarcón

Reputation: 3638

If you need to take into account duplicates you could use tally in combination with <= to compare the result Hash.

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

a2.tally <= a1.tally
# => false

a2.tally <= [5, 1, 6, 15, 2, 8]
# => true, a2 is a subset of the other array

Upvotes: 0

Jamie Birch
Jamie Birch

Reputation: 6112

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

Upvotes: 0

Geo
Geo

Reputation: 96997

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

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

b - a
# => [15]

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

Upvotes: 381

Charles Breton
Charles Breton

Reputation: 41

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

Upvotes: 2

Jon Snow
Jon Snow

Reputation: 11890

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

Upvotes: 2

Holger Just
Holger Just

Reputation: 55908

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).

Upvotes: 65

ayckoster
ayckoster

Reputation: 6857

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.

Upvotes: 0

Confusion
Confusion

Reputation: 16861

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) }

Upvotes: 13

Pablo Fernandez
Pablo Fernandez

Reputation: 105258

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).

Upvotes: 96

Related Questions