CODEWITHSUNDEEP
rubyarrays
Dercni
Dercni

Reputation: 1224

Finding arrays within arrays

I have an array of hashes, some of which are subsets of others.

a = []
a << {Bob: 1, Mary: 2, Sue: 3}
a << {Bob:1}
a << {Phil: 2, Brian: 8}
a << {Bob: 1, Mary: 2, Sue: 3, Tony: 9}

I need to return an array of the unique super-sets which, in this case, would be:

{Bob: 1, Mary: 2, Sue: 3, Tony: 9}
{Phil: 2, Brian: 8}

I read "Ruby Array Comparison Tricks" however it doesn't offer what I require.

Is there a Ruby solution to compare arrays and identify sub-arrays?

Upvotes: 1

Views: 60

Answers (1)

histocrat
histocrat

Reputation: 2381

I don't know a great algorithm for this, but the brute force solution is pretty simple in Ruby: use the - operator to find the complement of one array in another, then check if it's empty. With casting so it works with hashes too, the code is something like

def superset?(ary1, ary2)
  ary1 != ary2 && (ary2.to_a - ary1.to_a) == []
end

def maximal_sets(arrays)
  arrays.reject{ |ary2| arrays.any?{ |ary1| superset?(ary1, ary2) } }
end

Upvotes: 1

Related Questions