Python - 迭代嵌套列表

Question

我昨天开始遇到了一个小但棘手的问题。

我手头有一个（可能是无限）嵌套的列表，像这样：

[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函数，但我看不出来。

Christoph

- Christoph

---

你很可能正在重复造轮子。在Python中有用于处理系统发育树的包，例如Biopython的Phylo（http://www.biopython.org/wiki/Phylo）或dendropy（http://pypi.python.org/pypi/DendroPy）。 - Thomas K

只是挑刺一下：你的列表可能具有“任意”深度，但不是“无限”深度。至少我不知道它怎么可能。 - Eric Wilson

每个分类单元都必须插入到最适合的位置。这听起来像是试图构建邻接树，这是一个不好的计划。查阅更多关于如何最佳构建系统发育树以及为什么最简单的方法也是最糟糕的方法的文献资料。 - pyvi

Answer 1

我会使用生成器：

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]

据我所见，这符合所述要求。如果有一些未明确的要求我没有完全理解（例如，如果每个子列表的第一个元素必须是标量），请澄清，我会更新解决方案。

- NPE

---

谢谢！看起来非常不错。 我列出的不止这些，我忘了提到顺序不重要，所以[1, [[5, 2], [3, 4]]] [1, [[2, 5], [3, 4]]]基本上是相同的树。 - Christoph

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