44

How can I check whether one array is a subset of another array, regardless of the order of elements?

a1 = [3, 6, 4]
a2 = [1, 2, 3, 4, 5, 6, 7, 8, 9]

...?

a1 is a subset of a2
user229044
  • 232,980
  • 40
  • 330
  • 338
MxLDevs
  • 19,048
  • 36
  • 123
  • 194
  • Oh, *which* structure. Best is probably sets, since that's what sets are good at--but as the variety of answers shows (and there are yet more options), it may not matter--depending on your needs. – Dave Newton May 12 '12 at 21:18
  • Can there be duplicates in a1 or a2? If there can be duplicates in a1, do there have to be the same number or more duplicates in a2? In other words, what should the result be if your variables have the values `a1 = [1, 1]` and `a2 = [1,2,3,4,5,6,7,8,9]`? – Mark Byers May 12 '12 at 21:23
  • Currently I don't expect duplicates, but I imagine I would end up working with sets that contains duplicate values where I actually want to say "dupes don't matter". Would that cause an issue with arrays? – MxLDevs May 12 '12 at 21:53
  • Possible duplicate of [Ruby: Array contained in Array, any order](http://stackoverflow.com/questions/3897525/ruby-array-contained-in-array-any-order) – Nick Roz Sep 12 '16 at 18:55

4 Answers4

75

Easiest may be:

(a1 - a2).empty?
Dave Newton
  • 158,873
  • 26
  • 254
  • 302
42

Use sets. Then you can use set.subset?. Example:

require 'set'

a1 = Set[3,6,4]
a2 = Set[1,2,3,4,5,6,7,8,9]

puts a1.subset?(a2)

Output:

true

See it working online: ideone

BinaryButterfly
  • 18,137
  • 13
  • 50
  • 91
Mark Byers
  • 811,555
  • 193
  • 1,581
  • 1,452
  • 2
    Another advantage of Set is that you can also check other properties, such as `proper_subset?` if you didn't want identical sets to return true. – Mark Thomas May 13 '12 at 00:36
35

The data structure you already have is perfect, just check the intersection:

(a1 & a2) == a1

Update: The comment discussing permutations is interesting and creative, but quite incorrect as the Ruby implementors anticipated this concern and specified that the order of the result is the order of a1. So this does work, and will continue to work in the future. (Arrays are ordered data structures, not sets. You can't just permute the order of an array operation.)

I do rather like Dave Newton's answer for coolness, but this answer also works, and like Dave's, is also core Ruby.

Community
  • 1
  • 1
DigitalRoss
  • 143,651
  • 25
  • 248
  • 329
  • 1
    Oh, just take the intersection and check. Didn't think of that lol – MxLDevs May 12 '12 at 21:18
  • I'm not certain if mine is really better, as it depends on the implemention being sort-stable. (Also on no duplicates, but the definition of the question as a set operation seems to imply that. I suppose one could sort both terms.) – DigitalRoss May 12 '12 at 21:19
  • 1
    I realize this answer is almost 4 years old, but this does not necessarily work. `a1 & a2` will give a **permutation** of a1, which if the elements are not in the same order, will give false when comparing it `==` to a1. For example, `a1=%w(a c); a2= %w(a b c); perm=a1&a2; (may give ['c','a']); perm==a1 => false`. What is guaranteed to work is `a1.permutation.include?(a1&a2)`. – istrasci Mar 03 '16 at 21:58
  • 1
    @istrasci, the core docs specify at http://ruby-doc.org/core-2.3.1/Array.html#method-i-26 that _The order is preserved from the original array._ This does work correctly _and will continue to do so_ in the future as this behavior is part of the specification of the `&` method on `Array.` It's therefore also not necessary to sort the result. – DigitalRoss May 16 '16 at 21:09
3

Perhaps not fast, but quite readable

def subset?(a,b)
  a.all? {|x| b.include? x}
end
finiteautomata
  • 3,753
  • 4
  • 31
  • 41