From: Robert Klemme <shortcutter@...>
Date: 2009-11-04T20:56:14+09:00
Subject: Re: How would you accomplish this?

2009/11/4 George George <george.githinji@gmail.com>:
> Given an array of arrays for example
> [["A", "B"], ["A", "B", "D", "C"], ["B", "D"], ["B", "C", "F", "E"],
> ["C", "F"], ["C", "E"], ["G"]]
>
> what would be a nice way of "merging" the items that seem to already be
> contained in another array. e.g.
> ["A","B"] and ["B", "D"] are subsets of ["A", "B", "D", "C"] I would
> like to drop the subsets  and be left with ["A", "B", "D", "C"] only.
>
> My approach was to use the set module in Ruby, and look for set
> membership using a pairwise comparison.
> I also thought maybe i should look for the largest set. and then check
> whether the rest of the sets are subsets of this set. if they are, then
> delete them.
>
> However i thought a better solution, or strategy may already exist.
> How would you accomplish this?

The approach using set size seems reasonable to reduce the number of
set comparisons.  You could do

require 'set'

arrs = [["A", "B"], ["A", "B", "D", "C"], ["B", "D"], ["B", "C", "F", "E"],
["C", "F"], ["C", "E"], ["G"]]

result = []

arrs.sort_by {|a| -a.size}.each do |a|
  s = a.to_set
  result << s unless result.any? {|rs| rs.superset? s}
end

p result

-> [#<Set: {"B", "C", "F", "E"}>, #<Set: {"A", "B", "D", "C"}>, #<Set: {"G"}>]

Kind regards

robert


-- 
remember.guy do |as, often| as.you_can - without end
http://blog.rubybestpractices.com/