justin wrote: > The title sounds too complex, but my question is actually simple. > > Suppose I have [1,2,3,4,5], then there are many ways of making > clustering. > Among them, I want to pair up terminals until there is only one left > at the end. > For example, ((((1,2),3),4),5), (1,(2,(3,(4,5)))), or (((1,2),(3,4)), > 5) would be legitimate ones. > > How do you think can I, using the modules of Python such as itertools > as much as possible, make all possible such clusterings?
Here's my first attempt: def cluster(items): if len(items) == 2: yield items return for i in range(len(items)-1): for c in cluster(items[:i] + (items[i:i+2],) + items[i+2:]): yield c def unique(items): seen = set() for item in items: if item not in seen: seen.add(item) yield item if __name__ == "__main__": for item in unique(cluster(tuple("abcd"))): print item Unfortunately I get a lot of duplicates :( You could define a kind of operator precedence using itertools.combinations(), but I think it suffers from the same problem as a 3 b 1 c 2 d and a 2 b 1 c 3 d would both result in ((a, b), (c, d)). -- http://mail.python.org/mailman/listinfo/python-list