Python - Iteration over nested lists

Question

I'm stuck on a small but tricky problem since yesterday.

What I have is a (possibly infinitely) nested list like this:

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

On each level the lists consist of two sublists, (I didn't use tuples because the lists will probably get arbitrary length in the next step) Now I want to insert an element in every possible position in this list and return an list of lists of all possible insertion positions. So if I insert 5, my output should look like:

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

The background: I'm trying to construct an phylogenetic tree by adding one taxon at a time. Each taxon has to be inserted at the position where it fits best.

What I got now is:

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

which does not produce the output I want, but comes somewhat close.

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

There should be an easy solution, perhaps involving lambda functions, but I just don't see it.

Christoph

Answer 1

I'd use a generator:

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

Please note that this returns more trees than listed in your example:

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

As far as I can see, this ahderes to the stated requirements. If there are some unstated requirements that I didn't quite get (e.g. if the first element of every sublist has to be a scalar), please clarify and I'll update the solution.