從遞歸函數產生

Question

所以讓我們說我有幾個節點。每個節點都有一個可以到達的節點列表。這個節點列表可以包含它自己。我需要做的是構建一個節點可以採用的長度爲n的所有可能路徑。

例如：讓我們假設一些事情。

• 我有節點A和節點B
• 我需要的是三長（無短）
• 節點A可以去自己和B節點
• 節點B可以去自己所有可能的路徑和節點A

假設然後我可以建立所有路徑是：

1. AA一個
2. AAB
3. ABA
4. ABB
5. BAA
6. BAB
7. BBA
8. BBB

這是我現在所擁有的代碼;它可以工作，但在我的實際情況中，我需要八條路徑，並且有很多節點。這顯然會導致一些性能問題。我碰到了一個32位版本的Python2.7上運行的MemoryError。我還沒有嘗試過64位版本。手頭上顯而易見的問題是我目前的實施。我想也許使用產量/發電機會有所幫助。會嗎？如果是這樣，我甚至會如何在我的情況下實施收益率？

此外，如果Python 3有一些功能可以實現我所要求的功能，我並不侷限於Python 2。 Python 2恰好是我表現最好的計算機上的東西。

PARTS = 3 

def dive(node, depth=0): 
    combos = [] 

    if depth >= PARTS - 1: 
     if node.key: 
      return ((node.key,),) 
     return() 

    for next_ in node.next_nodes: 
     for combo in dive(next_, depth=depth+1): 
      if not node.key: 
       continue 
      combos.append((node.key,) + combo) 
    return combos 

Answer 1

則可以將當前解決方案的最簡單的方法，通過改變收益轉換爲發電機呼籲收益率......這就足夠......它可能不是也..也有一些graphtraversal庫赫然出現以及如果你的目標只是爲了解決問題，可以很好地解決這個問題

PARTS = 3 

def dive(node, depth=0): 
    combos = [] 

    if depth >= PARTS - 1: 
     if node.key: 
      #return ((node.key,),) 
      yield ((node.key,),) 
     #return() 
     yield() 
    for next_ in node.next_nodes: 
     for combo in dive(next_, depth=depth+1): 
      if not node.key: 
       continue 
      combos.append((node.key,) + combo) 
    #return combos 
    yield combos 

for result in dive(node): 
    print result