Python - Iterating over Nested Lists

Question

I am stuck on a small but complex problem since yesterday.

I have a (possibly infinitely) nested list:

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

At each level, lists consist of two subscriptions, (I did not use tuples because the lists are likely to be of arbitrary length in the next step) Now I want to insert an element at every possible position in this list and return a list of lists of all possible insertion positions. So if I insert 5, my output should look like this:

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

Background: I am trying to build a phylogenetic tree by adding one taxon at a time. Each taxon should be inserted in the position in which it is best suited.

Now I have:

 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 that I want, but is a bit 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 a simple solution, possibly using lambda functions, but I just don't see it.

Christophe

Answer 1

I would 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 

Note that this returns more trees than indicated 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 meets the specified requirements. If there are some undefined requirements that I did not quite understand (for example, if the first element of each sublist must be a scalar), specify and I will update the solution.