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 -- http://mail.python.org/mailman/listinfo/python-list