eubt.py

def lists_to_newick(g):
    if type(g)==str:
        return g
    else:
        s=''
        for x in g:
            s+=lists_to_newick(x)
            s+=','
    return '(%s)'%(s[:-1])



def LR(x):
    n=2**(len(x)-1)
    for i in xrange(1,n):
        L,R=[],[]
        for j in xrange(len(x)):
            if i%2==0:
                L.append(x[j])
            else:
                R.append(x[j])
            i=i/2
        yield L,R
    
def trees(z):
    if len(z)==2:
        yield [z[0],z[1]]
    elif len(z)==1:
        yield z[0]
    else:
        for (L,R) in LR(z):
            for left_subtree in trees(L):
                for right_subtree in trees(R):
                    yield [left_subtree,right_subtree]

   
#z=['a','b','c','d']
    
#x=z[1:]

#for t in trees(x):
#    print '(%s)%s;'%(lists_to_newick(t),z[0])