<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)