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?
answered May 12, 2012 at 21:16
-
1
-
2
setis stdlib, so it's arguable to say that it is less pure that using list differences. Commented Jun 13, 2016 at 14:29 -
2This is the right answer, since it prevents initialization of new objects, and clogging of memory. Here only the intersect is created.– AlgoriniCommented Aug 24, 2018 at 18:18
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
answered May 12, 2012 at 21:16
-
2Another 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. Commented May 13, 2012 at 0:36
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.
answered May 12, 2012 at 21:17
-
1Oh, just take the intersection and check. Didn't think of that lol– MxLDevsCommented May 12, 2012 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.) Commented May 12, 2012 at 21:19
-
1I realize this answer is almost 4 years old, but this does not necessarily work.
a1 & a2will 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 isa1.permutation.include?(a1&a2).– istrasciCommented Mar 3, 2016 at 21:58 -
1@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 onArray.It's therefore also not necessary to sort the result. Commented May 16, 2016 at 21:09 -
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.– Eric GuoCommented Apr 10 at 2:15
Perhaps not fast, but quite readable
def subset?(a,b)
a.all? {|x| b.include? x}
end
answered Oct 3, 2014 at 15:53
-
1
x.in? balso works with ActiveSupport. (stackoverflow.com/a/10601055/4960855)– EliadLCommented Dec 11, 2019 at 9:32
a1 = [1, 1]anda2 = [1,2,3,4,5,6,7,8,9]?