From: brabuhr@...
Date: 2009-11-26T07:31:23+09:00
Subject: Re: Distinct Sets (#225)

Sorry for all the posts :-) I think I'm done now.  I refined the
complex, non-elegant solution a bit more; so, to make it easy to
reference later, here are my three main solutions:

First:

require 'set'

class Set
  def intersect?(other)
    other.each { |o| return true if include?(o) }
    false
  end
end

def distinct_sets(array_of_arrays)
  set_of_sets = array_of_arrays.map{|a|
    a.to_set
  }.to_set

  set_of_sets.divide{|i, j|
    i.intersect?(j)
  }.map{|s|
    s.flatten.to_a.sort
  }
end

Third:

def distinct_sets(sets)
  sets = sets.dup
  values = sets.flatten.sort.uniq
  flag = true
  while flag
    flag = false
    sets = values.map{|v|
      sets.select{|s|
        s.include?(v)
      }.tap{|s|
        flag = true if s.size > 1
      }.flatten.sort.uniq
    }.uniq
  end
  sets
end

Second (from the earlier post):

def distinct_sets(sets)
  sets = sets.dup
  h1 = {}; h2 = {}
  sets.each{|s|
    h1[s.object_id] = s.dup
    s.each{|e| (h2[e] ||= []) << s.object_id}
  }
  merges = h2.select{|_, ids|
    ids.size > 1
  }.map{|_, ids| ids}
  return sets.sort.uniq if merges.size == 0
  flag = true
  while flag
    flag = false
    merges = h1.keys.map{|id|
      merges.select{|m|
        m.include?(id)
      }.tap{|m|
        flag = true if m.size > 1
      }.flatten.uniq
    }.uniq
  end
  result = []
  merges.each{|m|
    result << m.map{|id|
      s = h1[id]; h1.delete(id); s
    }.flatten.sort.uniq
  }
  (result + h1.values).sort.uniq
end

Second (refined version):

def distinct_sets(sets)
  sets = sets.dup
  h1 = {}; h2 = {}
  sets.each{|s|
    h1[s.object_id] = s.dup
    s.each{|e| (h2[e] ||= []) << s.object_id}
  }
  merges = h2.values.sort.uniq
  flag = true
  while flag
    flag = false
    merges = h1.keys.map{|id|
      merges.select{|m|
        m.include?(id)
      }.tap{|m|
        flag = true if m.size > 1
      }.flatten.sort.uniq
    }.sort.uniq
  end
  merges.map{|m|
    m.map{|id|
      s = h1[id]; h1.delete(id); s
    }.flatten.sort.uniq
  }
end