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

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]

就我所见，这个方法符合你说的要求。如果还有一些我没理解的要求（比如每个子列表的第一个元素必须是一个单一的值），请告诉我，我会更新这个解决方案。