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
4 Answers
Easiest may be:
(a1 - a2).empty?
3 Comments
Pankaj Tyagi
This is pure ruby and does not need
require "set"
rewritten
set is stdlib, so it's arguable to say that it is less pure that using list differences.
Algorini
This is the right answer, since it prevents initialization of new objects, and clogging of memory. Here only the intersect is created.
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
1 Comment
Mark Thomas
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.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.
5 Comments
MxLDevs
Oh, just take the intersection and check. Didn't think of that lol
DigitalRoss
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.)
istrasci
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).DigitalRoss
@istrasci, the core docs specify at 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.
Eric Guo
sorry, this method is wrong, it possible a1=[1,2,3];sub_a1=[2,1];(a1&sub_a1)==a1 equal false as it need sort first then compare.
Perhaps not fast, but quite readable
def subset?(a,b)
a.all? {|x| b.include? x}
end
1 Comment
EliadL
x.in? b also works with ActiveSupport. (stackoverflow.com/a/10601055/4960855)
a1 = [1, 1]anda2 = [1,2,3,4,5,6,7,8,9]?