How to populate all possible hierarchical clusterings from a set of elements?

[Richard Thomas]

On Jan 13, 10:02 am, Alain Ketterlin <al... at dpt-info.u-strasbg.fr>
wrote:
> justin <justpar... at 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.