On Jan 13, 10:02 am, Alain Ketterlin <al...@dpt-info.u-strasbg.fr> wrote: > justin <justpar...@gmail.com> writes: > > 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. > > Are you trying "ascending hierarchical clustering" by any chance? In > that case you're supposed to use some kind of distance to select the > (unique) pair of elements to merge at each step. > > > 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? > > I don't know about itertools, but the basic idea is: > > def clusterings(l): > if len(l) == 1: > print repr(l) > else: > n = len(l) > for i in xrange(n): > for j in xrange(i+1,n): > clusterings(l[:i]+l[i+1:j]+l[j+1:]+[[l[i],l[j]]]) > > Test this with: > > import sys > clusterings([i for i in xrange(int(sys.argv[1]))]) > > Do you realize there are *many* such clusterings? (the exact number > should be (n!)*((n-1)!)/2^(n-1) given the code above, if I'm not > mistaken.) > > -- Alain.
Actually the number of such "clusterings" is the (n-1)th Catalan number. http://en.wikipedia.org/wiki/Catalan_numbers Chard. -- http://mail.python.org/mailman/listinfo/python-list
