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

[Alain Ketterlin]

justin <justpark78 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.