Python - 迭代嵌套列表

自从昨天以来，我陷入了一个小而棘手的问题。Python - 迭代嵌套列表

我所拥有的是一个（可能无限）嵌套表是这样的：

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

每个级别上的列表包括两个子表，（我没有使用元组，因为该名单可能会得到任意长度在下一步中）现在我想在此列表中的每个可能位置插入一个元素，并返回所有可能插入位置列表的列表。所以，如果我插入5，我的输出应该是这样的：

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

背景：我试图通过在每次添加一个类群来构建系统发育树。每个分类单位必须插入最合适的位置。

我现在得到的是：

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

不产生我想要的输出，但说到有点接近。

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

应该有一个简单的解决方案，可能涉及lambda函数，但我只是没有看到它。

克里斯托夫

来源

2011-07-27 Christoph

你几乎肯定会重新发明轮子。 Python中有处理进化树的软件包，比如Biopython的Phylo（http://www.biopython.org/wiki/Phylo）或dendropy（http://pypi.python.org/pypi/DendroPy） –

只是挑剔的：你的列表可能具有*任意*深度，但不具有*无限*深度。至少，我不知道如何。 –

“每个分类单位必须插入最合适的位置。”这听起来像试图构建一个邻居加入树，这是一个不好的计划。查找更多关于如何最好地构建系统发育树的文献，以及为什么最简单的方法也是最差的。 – pyvi

我会使用一个发电机：

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

请注意，这个返回的树木超过在您的示例所示：

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

据我所看到的，这符合规定的要求。如果有一些未明确提出的要求我没有得到（例如，如果每个子列表的第一个元素必须是标量），请澄清，我将更新解决方案。

来源

2011-07-27 12:45:34 NPE

谢谢！这看起来非常好。它不止是我列出的，我忘记提到订单是不重要的，所以 [1，[[5,2]，[3,4]]] [1，[[2,5]，[3 ，4]]] 基本上是一样的树。 – Christoph

如果我删除第二个yield [nwklist] + [newid]行，我就得到了我想要的。非常感谢！ – Christoph

Python - 迭代嵌套列表

回答

相关问题