Получить структуру рекурсивным способом

Question

Есть словарь следующего вида и список ключей:

prep_dict = {1:0, 2:0,
             3:1, 4:1,
             5:2, 6:2,
             7:3, 8:3,
             9:5, 10:5,
             11:6, 12:6
             }
keys = [4, 7, 8, 9, 10, 11, 12]

Пытаюсь получить следующую структуру:

result = {
          4:[1, 0], 
          7:[3, 1, 0], 
          8:[3, 1, 0], 
          9:[5, 2, 0], 
          10:[5, 2, 0], 
          11:[6, 2, 0], 
          12:[6, 2, 0]
          }

Мой алгоритм действий следующий:

Сначала инициализирую result = defaultdict(list) из модуля collections. Далее, итерируюсь по ключам keys и для каждого ключа возвращаю его значение в словаре и добавляю в словарь по умолчанию по ключу. Повторяю эту операцию до тех пор, пока значение не будет равным нулю. Так как это действие повторяющееся, то можно обернуть его в рекурсию. Базовым случаем является равенство значения нулю.

Например для числа 9 из keys мы извлекаем значение 5 и добавляем его в список result. Далее, повторяем операцию для числа 5, ему соответствует значение 2, которое тоже добавляем в result[9]. Повторяем для 2, возвращаем 0, который добавляем в result[9]. В итоге result будет выглядеть следующим образом:

{9:[5, 2, 0]}

Тут я застрял и не могу продвинуться дальше.

Как именно реализовать рекурсию?

Answer 1

Одной рекурсии тут будет недостаточно. Та часть алгоритма, что вы описали, правильно находит один элемент из результата.

Нужно еще сделать внешний цикл по всем элементам из prep_dict, чтобы построить первое приближение решения (оно будет включать все элементы, в этом примере 1, 2, 3, 5, 6). В цикле вызывать рекурсивную процедуру, что вы описали.

Дале нужно удалить элементы, которые встречаются в списках. Для этого можно сделать либо отдельно цикл, чтобы их найти. Либо сама рекурсивная процедура может их собирать. Ну и собственно в конце нужно эти элементы удалить.

Answer 2

Корявое решение, но работает:

def construct_list_of_keys(key, prep_dict, res_list = []):
    if( key == 0 ):
        return res_list.append(key) #В конце добавляем 0
    res_list.append(key) #На каждом шаге добавляем текущий ключ
    get_dict(prep_dict[key], prep_dict, res_list) #Рекурсивный вызов
    return res_list[1:] #Возврат результата без самого первого ключа

def search_by_key(keys, prep_dict): 
    result = {} 
    for key in keys: #Пробегает по каждому ключу в keys 
       result[key] = get_dict(key, prep_dict, [])
    return result

Тогда вызов функции выглядит так:

result = search_by_key(keys, prep_dict)

В result будет нужный вам словарь

Answer 3

Решение с простой рекурсивной функцией:

def f(data, key, res=[]):
    val = data.get(key)
    if val is None:
        return res
    return res + [val] + f(data, val, res)

res = {key:f(prep_dict, key, []) for key in keys}

результат:

In [9]: res
Out[9]:
{4: [1, 0],
 7: [3, 1, 0],
 8: [3, 1, 0],
 9: [5, 2, 0],
 10: [5, 2, 0],
 11: [6, 2, 0],
 12: [6, 2, 0]}

Answer 4

Два решения - с использованием функции и цикла while. Предполагается, что все ключи из keys есть в prep_dict.

Вариант №1

def path_lst(key):
    if key == 0:
        return [0] 
    return [key] + path_lst(prep_dict[key])

result = {}
for key in keys:
    result[key] = path_lst(prep_dict[key])

Вариант №2

result = {}
for key in keys:
    result[key] = []
    tmp_key = key
    while tmp_key:
        result[key].append(prep_dict[tmp_key])
        tmp_key = prep_dict[tmp_key]

Output

{4: [1, 0],
 7: [3, 1, 0],
 8: [3, 1, 0],
 9: [5, 2, 0],
 10: [5, 2, 0],
 11: [6, 2, 0],
 12: [6, 2, 0]}

БЛОГ НА HUSL

Получить структуру рекурсивным способом

Ответы (4 шт):