my_iterators.py

class Tree:
    def __init__(self,taxa):
        self.taxa=taxa[1:]
        self.root=taxa[0]
        self.I=self.trees(self.taxa)
        
        
        
    def __iter__(self):
        return self
        
    def next(self):
        return '(%s)%s;'%(self.lists_to_newick(self.I.next()),self.root)
    

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


    def LR(self,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(self,z):
        if len(z)==2:
            yield [z[0],z[1]]
        elif len(z)==1:
            yield z[0]
        else:
            for (L,R) in self.LR(z):
                for left_subtree in self.trees(L):
                    for right_subtree in self.trees(R):
                        yield [left_subtree,right_subtree]