<brabuhr / gmail.com>:
>> Here's my not-fast solution:
Benoit Daloze <eregontp / gmail.com>:
> I must admit is a very elegant solution.

Here's a fresh non-elegant solution:

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

Slight bug in this version, (sometimes) adds an empty set to "result", e.g.:
  [ [], ["B", "C", "D", "F", "G", "J", "K", "L", "M", "N", "Q"], ["E", "H"] ]


ruby 1.8.7 (2009-06-12 patchlevel 174) [i486-linux]
                                              user     system
total        real
elements * sets: 1 * 5 => 1 * 1           0.010000   0.000000
0.010000 (  0.008809)
elements * sets: 1 * 5 => 2 * 1           0.000000   0.000000
0.000000 (  0.008136)
elements * sets: 2 * 5 => 3 * 1           0.010000   0.000000
0.010000 (  0.007661)
elements * sets: 2 * 5 => 4 * 1           0.010000   0.000000
0.010000 (  0.007797)
elements * sets: 2 * 5 => 5 * 1           0.010000   0.000000
0.010000 (  0.008351)
elements * sets: 3 * 5 => 6 * 1           0.010000   0.000000
0.010000 (  0.008181)
elements * sets: 3 * 5 => 7 * 1           0.010000   0.000000
0.010000 (  0.011584)
elements * sets: 3 * 5 => 8 * 1           0.010000   0.000000
0.010000 (  0.011224)
elements * sets: 4 * 5 => 9 * 1           0.010000   0.000000
0.010000 (  0.011744)
elements * sets: 4 * 5 => 10 * 1          0.020000   0.000000
0.020000 (  0.014110)
elements * sets: 18 * 255 => 1 * 51       0.630000   0.100000
0.730000 (  0.752032)
elements * sets: 35 * 255 => 2 * 51       1.760000   0.230000
1.990000 (  2.104564)
elements * sets: 52 * 255 => 3 * 51       2.230000   0.330000
2.560000 (  2.578473)
elements * sets: 69 * 255 => 4 * 51       2.760000   0.400000
3.160000 (  3.179041)
elements * sets: 86 * 255 => 5 * 51       3.230000   0.520000
3.750000 (  3.770260)
elements * sets: 103 * 255 => 6 * 51      3.740000   0.560000
4.300000 (  4.326179)
elements * sets: 120 * 255 => 7 * 51      4.250000   0.630000
4.880000 (  4.919036)
elements * sets: 137 * 255 => 8 * 51      4.870000   0.700000
5.570000 (  5.998519)
elements * sets: 154 * 255 => 9 * 51      5.350000   0.710000
6.060000 (  6.334980)
elements * sets: 171 * 255 => 10 * 51     5.960000   0.700000
6.660000 (  6.852846)
elements * sets: 34 * 505 => 1 * 101      2.200000   0.310000
2.510000 (  2.528937)
elements * sets: 68 * 505 => 2 * 101      6.230000   0.860000
7.090000 (  7.158239)
elements * sets: 102 * 505 => 3 * 101     8.130000   1.290000
9.420000 ( 10.024654)
elements * sets: 135 * 505 => 4 * 101    10.190000   1.370000
11.560000 ( 12.229713)
elements * sets: 169 * 505 => 5 * 101    12.060000   1.710000
13.770000 ( 14.657392)
elements * sets: 203 * 505 => 6 * 101    13.870000   2.060000
15.930000 ( 16.317533)
elements * sets: 236 * 505 => 7 * 101    15.860000   2.310000
18.170000 ( 18.707348)
elements * sets: 270 * 505 => 8 * 101    17.610000   2.750000
20.360000 ( 20.495151)
elements * sets: 304 * 505 => 9 * 101    19.780000   2.880000
22.660000 ( 23.630379)
elements * sets: 337 * 505 => 10 * 101   22.020000   2.980000
25.000000 ( 26.895880)

    per
set set user     system      total        real
10, 1  0.000000   0.000000   0.000000 (  0.000205)
10, 10  0.000000   0.000000   0.000000 (  0.000565)
10, 100  0.010000   0.000000   0.010000 (  0.004842)
10, 1000  0.070000   0.000000   0.070000 (  0.069138)
10, 10000  0.770000   0.100000   0.870000 (  0.872998)
10, 100000 18.600000   1.130000  19.730000 ( 19.776977)
      user     system      total        real
1, 10  0.000000   0.000000   0.000000 (  0.000126)
10, 10  0.000000   0.000000   0.000000 (  0.000569)
100, 10  0.010000   0.000000   0.010000 (  0.007341)
1000, 10  1.360000   0.040000   1.400000 (  1.419874)
10000, 10 (> 3 minutes)
      user     system      total        real
1, 1  0.000000   0.000000   0.000000 (  0.000044)
10, 10  0.000000   0.000000   0.000000 (  0.000587)
100, 100  0.080000   0.010000   0.090000 (  0.077950)
1000, 1000 (> 3 minutes)