Python - Iteración sobre listas anidadas

Question

Estoy atascado en un problema pequeño pero difícil desde ayer.

Lo que tengo es una (posiblemente infinito) Lista anidado como este:

[1,[2,[3,4]]] 
or [[1,2],[3,4]] and so on. 

En cada nivel las listas consisten en dos sublistas, (no hice uso de tuplas porque las listas probable que obtener una longitud arbitraria en el próximo paso) Ahora quiero insertar un elemento en cada posición posible en esta lista y devolver una lista de todas las posibles posiciones de inserción. Así que si inserto 5, mi salida debería verse como:

[ [5,[1,[2,[3,4]]]], 
[1,[5,[2,[3,4]]]], 
[1,[2,[5,[3,4]]]], 
[1,[2,[[3,5],4]]], 
[1,[2,[3,[4,5]]]] ] 

El fondo: Estoy tratando de construir un árbol filogenético mediante la adición de un taxón a la vez. Cada taxón debe insertarse en la posición en la que se ajuste mejor.

Lo que tengo ahora es:

def get_trees(nwklist,newid): 
    if not isinstance(nwklist,list): 
     return [newid,nwklist] 
    else: 
     return [newid,nwklist],[get_trees(nwklist[0],newid),nwklist[1]],[nwklist[0],get_trees(nwklist[1],newid)] 

que no produce la salida que quiero, pero llega un poco cerca.

([5, [1, [2, [3, 4]]]], 
[[5, 1], [2, [3, 4]]], 
[1, ([5, [2, [3, 4]]], [[5, 2], [3, 4]], [2, ([5, [3, 4]], [[5, 3], 4], [3, [5, 4]])])]) 

Debería haber una solución fácil, quizás con funciones lambda, pero simplemente no la veo.

Christoph

Answer 1

que haría uso de un generador:

def gen_trees(nwklist, newid): 
    yield [newid] + [nwklist] 
    if isinstance(nwklist, list): 
    for i in xrange(len(nwklist)): 
     for l in gen_trees(nwklist[i], newid): 
     yield nwklist[:i] + [l] + nwklist[i+1:] 
    yield [nwklist] + [newid] 

for l in gen_trees([1,[2,[3,4]]] , 5): 
    print l 

Tenga en cuenta que esto devuelve más árboles de los que aparecen en su ejemplo:

[5, [1, [2, [3, 4]]]] 
[[5, 1], [2, [3, 4]]] 
[[1, 5], [2, [3, 4]]] 
[1, [5, [2, [3, 4]]]] 
[1, [[5, 2], [3, 4]]] 
[1, [[2, 5], [3, 4]]] 
[1, [2, [5, [3, 4]]]] 
[1, [2, [[5, 3], 4]]] 
[1, [2, [[3, 5], 4]]] 
[1, [2, [3, [5, 4]]]] 
[1, [2, [3, [4, 5]]]] 
[1, [2, [[3, 4], 5]]] 
[1, [[2, [3, 4]], 5]] 
[[1, [2, [3, 4]]], 5] 

Por lo que yo puedo ver, esto ahder a los requisitos establecidos. Si hay algunos requisitos no declarados que no obtuve (por ejemplo, si el primer elemento de cada sublista tiene que ser un escalar), aclare y actualizaré la solución.