Finding arrays within arrays

Question

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?

What code have you written? Are you always keying off the first name/value pair? — the Tin Man
– the Tin Man, Commented Nov 19, 2014 at 22:48
You might be able to simplify things by using sets ruby-doc.org/stdlib-2.1.5/libdoc/set/rdoc/Set.html — cciollaro
– cciollaro, Commented Nov 19, 2014 at 22:49

histocrat · Accepted Answer · 2014-11-19 22:48:30Z

1

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

answered Nov 19, 2014 at 22:48

histocrat

2,41114 silver badges26 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Finding arrays within arrays

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related