Grouping pairs - suggested tools

Peter Otten __peter__ at web.de
Tue Sep 21 17:31:32 CEST 2010


Astley Le Jasper wrote:

> Thanks all. I was playing around with this and came up with another
> solution using dictionaries (... comfort zone ...!!)

> from operator import itemgetter
> 
> def group_stuff(data):
> 
>     group_dic = {}
>     group_id = 0
> 
>     for line in data:
>         i = 0
>         for ref in line:
>             if group_dic.get(ref) is None:
>                 if group_dic.get(line[1-i]) is not None:
>                     group_id = group_dic[line[1-i]]
>                 else:
>                     group_id +=1
>                 group_dic[ref] = group_id
>             i+=1
> 
>     group_list = []
>     for id, group in sorted(group_dic.items(), key=itemgetter(1,0)):
>         group_list.append((group, id))
> 
>     return group_list
> 
> if __name__ == '__main__':
>     data = [('a','b'),('a','c'),('a','d'),('b','c'),('b','d'),
> ('c','d'),('e','f'),('e','g'),('f','g'),('h','i')]
>     grouped = group_stuff(data)
>     print grouped

> Output: [(1, 'a'), (1, 'b'), (1, 'c'), (1, 'd'), (2, 'e'), (2, 'f'),
> (2, 'g'), (3, 'h'), (3, 'i')]

I think you have the same bug as Alf's code, you never merge existing 
groups. Have you tried Arnaud's counterexample?

By the way, are ('a', 'b') and ('b', 'a') to be considered equivalent for 
your problem?

Peter



More information about the Python-list mailing list