Menu
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
953
Simple Approach: A simple approach is to run two nested loops and generate all subarrays of the array A[] and use one more loop to check if any of the subarray of A[] is equal to the array B[]. Efficient Approach : An efficient approach is to use two pointers to traverse both the array simultaneously.
Simple: use array subtraction. On array subtraction, you will know whether or not one array is a subset of the other. You can use array_intersect also. array_diff(['a', 'b', 'c'], ['a', 'b']) will return ['c'].
first is a property of an array in Ruby that returns the first element of an array. If the array is empty, it returns nil. array. first accesses the first element of the array, i.e., the element at index 0 .
Easiest may be:
(a1 - a2).empty?
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
39
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.
33
Perhaps not fast, but quite readable
def subset?(a,b)
a.all? {|x| b.include? x}
end
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
