рекурсивные функции на список кортежей

Question

Я следующую задачу:

Прежде всего, у меня есть список кортежей, как следующее:

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

Чтобы сделать вещи проще, скажем, что первый число в каждом кортеже «управляет» вторым (для тех, кто знаком с анализом зависимостей, первое число представляет собой индекс головы, а второй - индекс зависимого).

Теперь то, что я хочу создать, это функция, которая принимает в качестве аргумента 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 

, но он не работает. Кто-нибудь может мне помочь?

Answer 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- списка> комплект-> немного избыточно, но потребовалось три секунды, чтобы записать: D

EDIT: Фактически, вы должны использовать набор. Это позволит избежать дубликатов.

Answer 2

>>> 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] 

Answer 3

функционального путь

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]  

Answer 4

Вы должны проверить это popular question, который может объяснить, почему использование изменяемых значений по умолчанию в вашей функции может быть причиной вам проблемы.

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