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

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), где на каждой итерации ваш выбор для следующего элемента ограничен теми, что указаны в карте [current_point].

источник

2012-01-18 Babak

Ну, вы пометили его с помощью рекурсии .. Вы пробовали это? – wim

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)

источник

2012-01-18 07:09:44

Прошу прощения, я забыл упомянуть, что карта [a] [b] - это целое число, представляющее расстояние между a и b. Таким образом, ваше решение перестает работать, как только оно попадает в целое число. Можете ли вы рассказать мне, как изменить его на точный эквивалент вложенного цикла? Таким образом, функция не выходит за пределы карты [a]. (карты [X] достаточно для любой точки X, так как ваш выбор о том, где вы можете идти дальше от определенной точки, не зависит от того, как вы туда попали) – Babak

Если map [a] [b] является целым числом, ваш оригинал код не может работать. Не могли бы вы обновить вопрос с помощью рабочего примера 'map'? Я добавлю вид «карты», который я принял на этот ответ. –

... и отредактируйте ответ, чтобы на самом деле работать, так как ни я, ни 5 первоопортов не заметили, что это не ... –

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

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 solution. Конечно, эта библиотека может вам помочь, см. Этот пример: Finds all shortest paths (geodesics) from a vertex to all other vertices.

С уважением.

источник

2012-01-18 08:22:36 danihp

Так же, как и другие предложили, с помощью рекурсии:

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)

источник

2012-01-18 10:50:59 Bogdan

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

ответ

Смежные вопросы