0

我有以下问题：

首先，我有一个元组列表，如下所示：

[(1,2),(2,3),(4,5),(5,6),(5,7),(5,8),(6,9),(6,10),(7,11),(12,14)]

为方便起见，假设每个元组中的第一个数字“控制”第二个数字（对于熟悉依赖解析的人来说，第一个数字代表头的索引，而第二个数字代表依赖的索引）。

现在我要创建的是以 an 作为参数的函数int和上面的列表。该函数必须查找所有将整数参数作为第一个数字的元组并返回第二个数字。然后该函数应该递归地获取这些第二个数字中的每一个，查看它作为第一个数字出现的元组是什么并返回第二个数字。这应该一直持续到无法检索到其他第二个数字。

我将用一个例子来更好地解释它：假设这个函数将数字 5 作为输入。第一个数字为 5 的元组是(5,6),(5,7),(5,8); 作为第一个结果，该函数应采用 6,7,8 并将其附加到list. 现在该函数应该考虑 6,7,8 ，查找它们作为第一个数字 ( (6,9),(6,10),(7,11)) 出现的元组并返回第二个数字 (9,10,11)。由于 8 在任何元组中都不是第一个数字，因此它的旅程在此阶段结束。返回的最终列表应该是[6,7,8,9,10,11].

我已经尝试过类似的方法，但它不起作用：

def foo(start_index, lista_tuples,list_to_return=list()):

    indeces=[x[1] for x in lista_tuples if x[0]==start_index]
    list_to_return.extend(indeces)
    for index in indeces:
              foo(index,lista_tuples,list_to_return)
    return list_to_return

但它不起作用。有人能帮我吗？

4

4 回答 4

1 
>>> L =[(1,2),(2,3),(4,5),(5,6),(5,7),(5,8),(6,9),(6,10),(7,11),(12,14)]
>>> def foo(start, L, answer=None):
...     if answer is None:
...         answer = []
...     answer += [i[1] for i in L if i[0]==start]
...     for i in (i[1] for i in L if i[0]==start):
...             foo(i, L, answer)
...     return answer
...
>>> print foo(5, L)
[6, 7, 8, 9, 10, 11]
于 2013-07-26T19:25:13.807 回答
1

在您的代码中，您总是迭代您找到的所有“第二个值”。这会产生无限递归。为避免这种情况，请从indeces已存在的所有值中删除list_to_return：

def foo(start_index, lista_tuples,list_to_return=list()):

    indeces=[x[1] for x in lista_tuples if x[0]==start_index]
    new_values = list(set(indeces) - set(list_to_return))
    list_to_return.extend(indeces)
    for index in new_values:
              foo(index,lista_tuples,list_to_return)
    return list_to_return

双重转换 list->set->list 有点矫枉过正，但写下来花了三秒钟 :D

编辑：事实上，你实际上应该使用一个集合。这将避免重复。

于 2013-07-26T19:25:24.197 回答
1

功能方式

def worker(n):
    data = []
    for j in [x[1] for x in l if x[0] == n]:
        data += [j] + worker(j)
    return data

print worker(5)
[6, 9, 10, 7, 11, 8]

程序方式

def worker(n, data):
    for j in [x[1] for x in l if x[0] == n]:
        data.append(j)
        worker(j, data)

d = []
worker(5, d)
print d
[6, 9, 10, 7, 11, 8]
于 2013-07-26T19:25:36.943 回答
0

你应该看看这个流行的问题，它可以解释为什么在你的函数中使用一个可变的默认值可能会导致你的问题。 

def foo(start_index, lista_tuples):
    return _foo(start_index, lista_tuples, [])

def _foo(start_index, lista_tuples,list_to_return):

    indeces=[x[1] for x in lista_tuples if x[0]==start_index]
    list_to_return.extend(indeces)
    for index in indeces:
              _foo(index,lista_tuples,list_to_return)
    return list_to_return
于 2013-07-26T19:35:21.263 回答