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

Had an epiphany while thinking about the last one I had sent :-)
The last half of the previous one can be applied directly to the input
array of arrays of items instead of to the intermediate array of
arrays of object ids:

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

Easier code, but generally scales more poorly than the previous more
complex version:

ruby 1.8.7 (2009-06-12 patchlevel 174) [i486-linux]
                                              user     system
total        real
elements * sets: 1 * 5 => 1 * 1           0.000000   0.000000
0.000000 (  0.001928)
elements * sets: 1 * 5 => 2 * 1           0.000000   0.000000
0.000000 (  0.002136)
elements * sets: 2 * 5 => 3 * 1           0.000000   0.000000
0.000000 (  0.003218)
elements * sets: 2 * 5 => 4 * 1           0.000000   0.000000
0.000000 (  0.003926)
elements * sets: 2 * 5 => 5 * 1           0.010000   0.000000
0.010000 (  0.007761)
elements * sets: 3 * 5 => 6 * 1           0.010000   0.000000
0.010000 (  0.012438)
elements * sets: 3 * 5 => 7 * 1           0.010000   0.000000
0.010000 (  0.009863)
elements * sets: 3 * 5 => 8 * 1           0.010000   0.000000
0.010000 (  0.015234)
elements * sets: 4 * 5 => 9 * 1           0.020000   0.000000
0.020000 (  0.022202)
elements * sets: 4 * 5 => 10 * 1          0.020000   0.000000
0.020000 (  0.025353)
elements * sets: 18 * 255 => 1 * 51       0.400000   0.120000
0.520000 (  0.514576)
elements * sets: 35 * 255 => 2 * 51       0.970000   0.180000
1.150000 (  1.280102)
elements * sets: 52 * 255 => 3 * 51       1.690000   0.210000
1.900000 (  2.260107)
elements * sets: 69 * 255 => 4 * 51       2.310000   0.390000
2.700000 (  2.888354)
elements * sets: 86 * 255 => 5 * 51       3.220000   0.460000
3.680000 (  4.250457)
elements * sets: 103 * 255 => 6 * 51      4.090000   0.590000
4.680000 (  4.723892)
elements * sets: 120 * 255 => 7 * 51      5.200000   0.600000
5.800000 (  6.258614)
elements * sets: 137 * 255 => 8 * 51      6.330000   0.700000
7.030000 (  7.694748)
elements * sets: 154 * 255 => 9 * 51      7.470000   0.870000
8.340000 (  8.730147)
elements * sets: 171 * 255 => 10 * 51     8.970000   0.820000
9.790000 (  9.871180)
elements * sets: 34 * 505 => 1 * 101      1.720000   0.250000
1.970000 (  2.331276)
elements * sets: 68 * 505 => 2 * 101      3.620000   0.750000
4.370000 (  4.983125)
elements * sets: 102 * 505 => 3 * 101     6.110000   0.920000
7.030000 (  7.258356)
elements * sets: 135 * 505 => 4 * 101     8.730000   1.460000
10.190000 ( 10.912860)
elements * sets: 169 * 505 => 5 * 101    12.130000   1.630000
13.760000 ( 14.714311)
elements * sets: 203 * 505 => 6 * 101    15.280000   2.040000
17.320000 ( 17.556731)
elements * sets: 236 * 505 => 7 * 101    19.090000   2.490000
21.580000 ( 22.005613)
elements * sets: 270 * 505 => 8 * 101    23.430000   2.620000
26.050000 ( 26.366511)
elements * sets: 304 * 505 => 9 * 101    28.090000   3.020000
31.110000 ( 32.421622)
elements * sets: 337 * 505 => 10 * 101   33.270000   3.550000
36.820000 ( 39.281699)

    per
set set user     system      total        real
10, 1  0.000000   0.000000   0.000000 (  0.000338)
10, 10  0.010000   0.000000   0.010000 (  0.006647)
10, 100  0.320000   0.000000   0.320000 (  0.326307)
10, 1000 (>3 minutes)
      user     system      total        real
1, 10  0.000000   0.000000   0.000000 (  0.000311)
10, 10  0.010000   0.000000   0.010000 (  0.006137)
100, 10  0.290000   0.020000   0.310000 (  0.305198)
1000, 10 77.240000   8.000000  85.240000 ( 90.868828)
10000, 10 (>3 minutes)
      user     system      total        real
1, 1  0.000000   0.000000   0.000000 (  0.000052)
10, 10  0.000000   0.000000   0.000000 (  0.006212)
100, 100 84.440000   1.080000  85.520000 ( 91.856640)
1000, 1000 (>3 minutes)