Лучший эквивалент этого сумасшедшего вложенного цикла python for

for a in map:
    for b in map[a]:
        for c in map[b]:
            for d in map[c]:
                for e in map[d]:
                    print a+b+c+d+e

Приведенный выше код используется для создания всех путей определенной длины в графе. map[a] представляет точки, до которых можно добраться из точки a.

Как я могу изменить его, чтобы имитировать произвольное количество циклов?

Это похоже на декартово произведение (itertools.product), где на каждой итерации ваш выбор следующего элемента ограничивается теми, что указаны в map[current_point].


python recursion nested-loops generator
person Babak    schedule 18.01.2012    source источник
comment
Ну, вы пометили это рекурсией... вы пробовали это?   -  person wim    schedule 18.01.2012

Ответы (3)


arrow_upward
3
arrow_downward

Это классическая рекурсивная задача. Ваша функция должна возвращать конкатенацию значения узла со всеми результатами вашей функции результата для каждого дочернего узла. Как видно из предложения, поведение функции объясняется рекурсивным образом:

myGraph = { 1:[2,3], 2:[3,4] }

def recorre( node_list, p = '' ):    
    for node in node_list:
        if node in myGraph and myGraph[node]: 
            recorre(myGraph[node], p+unicode( node ))
        else:
            print p+unicode( node )

recorre( myGraph )

Результат:

>>> recorre( myGraph )
123
124
13
23
24

Этот код является отправной точкой. Вы можете хранить все пути в списке, использовать генератор yield и т. д. Не забудьте предотвратить круги.

Кроме того, обратите внимание на решение igraph. Конечно, эта библиотека может вам помочь, см. этот пример: Находит все кратчайшие пути (геодезические) из вершина ко всем другим вершинам.

С Уважением.

person dani herrera    schedule 18.01.2012

arrow_upward
1
arrow_downward

Как и другие предложенные, с рекурсией:

    distances = []        

    def compute_distance(map, depth, sum):
         if depth == 0 or len(map) == 0:
            distances.append[sum]
         else:
            for a in map:
               compute_distance(map[a], depth - 1, sum + a)

   compute_distance(map, x, 0)
person Bogdan    schedule 18.01.2012

arrow_upward

arrow_downward

person    schedule
comment
Извините, я забыл упомянуть, что map[a][b] — это целое число, представляющее расстояние между a и b. Таким образом, ваше решение перестает работать, как только оно достигает целого числа. Можете ли вы сказать мне, как изменить его на точный эквивалент вложенного цикла? Таким образом, функция не выходит за пределы map[a]. (карты [X] достаточно для любой заданной точки X, поскольку ваш выбор того, куда вы можете пойти дальше из определенной точки, не зависит от того, как вы туда попали) - person Babak; 18.01.2012
comment
Если map[a][b] является целым числом, исходный код не может работать. Не могли бы вы обновить вопрос рабочим примером map? Я добавлю вид map, который я предполагал к этому ответу. - person Baffe Boyois; 18.01.2012
comment
... и отредактируйте ответ, чтобы он действительно работал, поскольку ни я, ни 5 голосующих не заметили, что это не так... - person Baffe Boyois; 18.01.2012