从递归函数产生

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