Python - Iteracja na listach zagnieżdżonych

Question

Utknąłem na małym, ale trudnym problemie od wczoraj.

Co mam to (być może nieskończenie) zagnieżdżone listy tak:

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

Na każdym poziomie listy składa się z dwóch podlist (nie używałem bo krotki list będzie prawdopodobnie uzyskać dowolną długość w następnym kroku) Teraz chcę wstawić element do każdej możliwej pozycji na tej liście i zwrócić listę list wszystkich możliwych pozycji wstawiania. Więc jeśli wkładki 5, moje wyjście powinno wyglądać następująco:

[ [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]]]] ] 

tle: Próbuję skonstruować drzewa filogenetycznego dodając jeden takson naraz. Każdy takson musi być wstawiony w miejscu, w którym najlepiej pasuje.

Co mam teraz jest:

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)] 

który nie produkuje wyjście chcę, ale przychodzi dość blisko.

([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]])])]) 

Powinno być proste rozwiązanie, być może obejmujące funkcje lambda, ale po prostu tego nie widzę.

Christoph

Answer 1

bym użyć generatora:

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 

proszę zauważyć, że zwraca więcej drzew niż wymienione w przykładzie:

[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] 

O ile widzę, to ogranicza się do podanych wymagań. Jeśli istnieją pewne nieokreślone wymagania, których nie otrzymałem (np. Jeśli pierwszy element każdej podlisty musi być skalarem), proszę wyjaśnić, a ja zaktualizuję rozwiązanie.