Python - Lặp lại trên danh sách lồng nhau

Question

Tôi đang mắc kẹt trên một vấn đề nhỏ nhưng phức tạp kể từ hôm qua.

gì tôi có là một (có thể là vô hạn) lồng danh sách như thế này:

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

Trên mỗi mức độ danh sách bao gồm hai danh sách phụ, (tôi không sử dụng các bộ vì danh sách có thể sẽ có được chiều dài tùy ý trong bước tiếp theo) Bây giờ tôi muốn chèn phần tử vào mọi vị trí có thể có trong danh sách này và trả về danh sách liệt kê tất cả các vị trí chèn có thể có. Vì vậy, nếu tôi chèn 5, sản lượng của tôi sẽ giống như thế:

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

Nền: Tôi đang cố gắng để xây dựng một cây phả hệ bằng cách thêm một đơn vị phân loại tại một thời điểm. Mỗi taxon phải được chèn vào vị trí phù hợp nhất.

Những gì tôi có bây giờ là:

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

mà không sản xuất đầu ra tôi muốn, nhưng đi kèm hơi gần.

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

Có một giải pháp dễ dàng, có thể liên quan đến các hàm lambda, nhưng tôi không thấy nó.

Christoph

Answer 1

Tôi muốn sử dụng một máy phát điện:

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 

Xin lưu ý rằng đây trả về nhiều cây hơn được liệt kê trong ví dụ của bạn:

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

Theo như tôi thấy, này ahderes để các yêu cầu đã nêu. Nếu có một số yêu cầu không được nêu ra mà tôi đã không nhận được (ví dụ: nếu phần tử đầu tiên của mỗi danh sách phụ phải là vô hướng), vui lòng làm rõ và tôi sẽ cập nhật giải pháp.