[perl-python] exercise: partition a list by equivalence

[Reinhold Birkenfeld]

Reinhold Birkenfeld wrote:

> My solution (which may not be the fastest or most effective, but till
> now is the shortest <wink> and it works):
> 
> def merge(pairings):
>     sets = {}
>     for x1, x2 in pairings:
>         newset = (sets.get(x1, frozenset([x1]))
>                   | sets.get(x2, frozenset([x2])))
>         for i in newset:
>             sets[i] = newset
> 
>     return [list(aset) for aset in set(sets.itervalues())]

A recursive solution (around twice as fast as the above, though very
slow still...)

def merge_rb2(pairings):
    def merge(sets):
        res_sets = []
        for tset in sets:
            for item in tset:
                for rset in res_sets:
                    if item in rset:
                        rset.update(item for item in tset)
                        break
                else:
                    continue
                break
            else:
                res_sets.append(set(tset))
        if len(res_sets) == len(sets):
            return res_sets
        else:
            return merge(res_sets)

    return [list(s) for s in merge([set(pair) for pair in pairings])]

Another one:

def merge_rb3(pairings):
    dic = {}
    for x1, x2 in pairings:
        dic.setdefault(x1, []).append(x2)
        dic.setdefault(x2, []).append(x1)

    def red(k, l):
        l.append(k)
        sub = dic[k]
        for i in dic[k]:
            if i not in l:
                red(i, l)
        del dic[k]

    res = []
    while len(dic):
        rl = []
        red(iter(dic).next(), rl)
        res.append(rl)

    return res

Reinhold