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 函数，但我只是没有看到它。

克里斯托夫

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]

据我所知，这符合规定的要求。如果有一些我不太明白的未说明的要求（例如，如果每个子列表的第一个元素必须是标量），请澄清，我将更新解决方案。