From: Benoit Daloze <eregontp@...>
Date: 2009-11-26T20:22:14+09:00
Subject: Re: Distinct Sets (#225)

--0016e65b62a6dc4d970479446241
Content-Type: text/plain; charset=ISO-8859-1

Here is my array-based combination solution:

def multiple(start)
    sets = start.uniq
    while (f=sets.flatten) && f != f.uniq
        sets.combination(2) { |(a, b)|
            if sets.include?(a) && sets.include?(b) && a != b && (a &
b).length > 0
                # include? ensure the set has not been mixed with another
one already
                # a != b ensure we are not playing with a == b, what would
delete a (and b) or not find the index
                sets[sets.index(a)] = (a | b)
                sets.delete(b)
            end
        }
    end
    sets.map { |s| s.sort }
end

It just combinate by 2 sets, and look if they can merge.
The while loop is then rarely met, because sets merge 2 by 2.

This solution is quite fast for small sets(as I said before, 0.22 for the
first test), but is completely out for larger sets.

This is another, using Array#partition to modify itself, while merging all
the elements with the common value in one iteration

def better(start)
    sets = start.dup
    f = sets.flatten
    (f.uniq.select { |e| f.count(e)>1 }).each { |reducing_on|
        i = sets.index { |set| set.include? reducing_on }
        sets2merge, sets = sets.partition { |set| set.include? reducing_on }
        sets.insert( i, sets2merge.inject(:|) )
    }
    sets.map { |s| s.sort }
end

2009/11/26 lith <minilith@gmail.com>

> > > Here is a graph-based approach:
> > >http://pastie.org/714759
> >
> > Running the small approximative benchmark:
>
> Here is a modified version that should have slightly improved runtime
> characteristics:
> http://pastie.org/715755
>
> Regards,
> Tom
>
>

--0016e65b62a6dc4d970479446241--