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]

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