更好的等效於這個瘋狂的嵌套python循環

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到達的點。更好的等效於這個瘋狂的嵌套python循環

我怎樣才能改變它來模擬有任意數量的循環？

這就像一個笛卡爾積（itertools.product），其中每次迭代您對下一個元素的選擇僅限於map [current_point]中的那些元素。

來源

2012-01-18 Babak

那麼，你有遞歸標記吧..你嘗試了嗎？ – wim 2012-01-18 07:11:55

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 2012-01-18 07:42:12

如果map [a] [b]是一個整數，代碼無法工作。你能用一個'map'的實例來更新這個問題嗎？我會添加我認爲這個答案的那種'map'。 – 2012-01-18 16:42:38

...並編輯實際工作的答案，因爲我和5個上級都沒有注意到它沒有...... – 2012-01-18 16:52:35

這是一個經典的遞歸問題。您的函數應該返回每個子節點的結果與所有函數結果的結果值的串聯。正如你可以看到一句話，函數的行爲在遞歸的方式解釋說：

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

更好的等效於這個瘋狂的嵌套python循環

回答

相關問題