Лучший эквивалент этого сумасшедшего вложенного питона для цикла - PullRequest
Новая
       11

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

8 голосов
/ 18 января 2012 
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

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

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

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

Ответы [ 3 ]

6 голосов
/ 18 января 2012 
map = {
    'a': ['b', 'c'],
    'b': ['c', 'd'],
    'c': ['d', 'a'],
    'd': []
}

def print_paths(map, start, length, prefix = ''):
    if length == 0:
        print prefix
    else:
        for a in map[start]:
            print_paths(map, a, length - 1, prefix + start)

for a in map.keys():
    print_paths(map, a, 5)
3 голосов
/ 18 января 2012

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

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 и т. Д. Не забудьте запретить круги.

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

Привет.

1 голос
/ 18 января 2012

Как и другие, с рекурсией: 

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