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
