Python - итерация по вложенным спискам - PullRequest
Новая
       5

Python - итерация по вложенным спискам

7 голосов
/ 27 июля 2011

Со вчерашнего дня я застрял в небольшой, но хитрой проблеме.

У меня есть (возможно, бесконечно) вложенный список, подобный этому: 

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

Должно быть простое решение, возможно, с использованием лямбда-функций, но я его просто не вижу.

Кристоф

1 Ответ

2 голосов
/ 27 июля 2011

Я бы использовал генератор: 

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]

Насколько я вижу, это ahderesк заявленным требованиям.Если есть некоторые неустановленные требования, которые я не совсем получил (например, если первый элемент каждого подсписка должен быть скалярным), уточните, и я обновлю решение.

...