Возврат списка путей к конечным узлам из вложенного списка списков.

Question

У меня есть динамическая c древовидная структура, представленная в виде списка списков - вот один из таких примеров с пробелами для иллюстрации структуры:

[['first',     
               [0, 'list1'], 
               [1, 'list2'], 
               [2, 'list3']],
 ['second',    
               ['second_subda', 
                      [0, 'tup1'], 
                      [1, 'tup2']],
               ['second_subdb', 
                      [0, 'tup3'], 
                      [1, 'tup4']]],
 ['third',
               ['third_subda',   
                      [0, 'a'],
                      [1, 'b'],
                      [2, 'c'],
                      [3, 
                            ['d',  
                                  [0, 'e'], 
                                  [1, 'f'], 
                                  [2, 
                                        ['g', 
                                               [0, 1], 
                                               [1, 2], 
                                               [2, 3]]]]]]]]

И я хочу извлечь Исходя из этого, все листовые узлы, а также пути, необходимые для их достижения:

например, из приведенной выше структуры, я хочу вернуть:

[ ( 'list1', ['first', 0 ] ) , 
  ( 'list2', ['first', 1 ] ) , 
  ( 'list3', ['first', 2 ] ) , 
  ( 'tup1' , ['second',  'second_subda', 0 ] ) ,
  ( 'tup2' , ['second',  'second_subda', 1 ] ) ,
  ( 'tup3' , ['second',  'second_subdb', 0 ] ) ,
  ( 'tup4' , ['second',  'second_subdb', 1 ] ) ,
  ( 'a'    , ['third',   'third_subda',  0 ] ) ,  
  ( 'b'    , ['third',   'third_subda',  1 ] ) ,  
  ( 'c'    , ['third',   'third_subda',  2 ] ) ,  
  ( 'e'    , ['third',   'third_subda',  3  , 'd',  0 ] ) ,  
  ( 'f'    , ['third',   'third_subda',  3  , 'd',  1 ] ) ,  
  (  1     , ['third',   'third_subda',  3  , 'd',  2 , 'g' , 0 ] ) ,  
  (  2     , ['third',   'third_subda',  3  , 'd',  2 , 'g' , 1 ] ) ,  
  (  3     , ['third',   'third_subda',  3  , 'd',  2 , 'g' , 2 ] )]

т.е. для каждого "листа" Я хочу извлечь кортеж, состоящий из всех значений листа и списка всех начальных записей списка, которые описывают уникальный путь для достижения этого элемента листа. Я должен остаться со списком этих кортежей, где количество элементов в списке соответствует количеству листовых узлов в дереве.

Я пытался построить это дерево в модуле, подобном networkx, но для моего варианта использования издержки дополнительного модуля излишни. Я просто хочу придерживаться ванильного python кода, где это возможно.

Answer 1

Вы можете использовать рекурсию с генератором:

data = [['first', [0, 'list1'], [1, 'list2'], [2, 'list3']], ['second', ['second_subda', [0, 'tup1'], [1, 'tup2']], ['second_subdb', [0, 'tup3'], [1, 'tup4']]], ['third', ['third_subda', [0, 'a'], [1, 'b'], [2, 'c'], [3, ['d', [0, 'e'], [1, 'f'], [2, ['g', [0, 1], [1, 2], [2, 3]]]]]]]]
def get_paths(d, c = []):
  for a, *b in d:
    if len(b) == 1 and not isinstance(b[0], list):
      yield (b[0], c+[a])
    else:
      yield from get_paths(b, c+[a])

print(list(get_paths(data)))

Выход:

[('list1', ['first', 0]), 
 ('list2', ['first', 1]), 
 ('list3', ['first', 2]), 
 ('tup1', ['second', 'second_subda', 0]), 
 ('tup2', ['second', 'second_subda', 1]), 
 ('tup3', ['second', 'second_subdb', 0]), 
 ('tup4', ['second', 'second_subdb', 1]), 
 ('a', ['third', 'third_subda', 0]), 
 ('b', ['third', 'third_subda', 1]), 
 ('c', ['third', 'third_subda', 2]), 
 ('e', ['third', 'third_subda', 3, 'd', 0]), 
 ('f', ['third', 'third_subda', 3, 'd', 1]), 
 (1, ['third', 'third_subda', 3, 'd', 2, 'g', 0]), 
 (2, ['third', 'third_subda', 3, 'd', 2, 'g', 1]), 
 (3, ['third', 'third_subda', 3, 'd', 2, 'g', 2])]

Answer 2

Во-первых, если вы можете, используйте для этого диктовку диктов, а не список списков. Словари имеют постоянное время поиска для ключей в отличие от списков, которые имеют линейное время поиска.

На ваш вопрос, каждый раз, когда вы имеете дело с динамическими c деревьями, обычно используется рекурсия.

Это работает с вашим деревом:

def get_leaf_paths(children: list, path_prefix:list=[], acc:list=[]):
    for child in children:
        path = path_prefix + [child[0]]
        if isinstance(child[1], list):
            get_leaf_paths(child[1:], path, acc)
        else:
            acc.append(
                (child[1], path)
            )
    return acc

get_leaf_paths(tree)

Однако это уродливо и не зря. Python не хочет, чтобы вы реализовывали такие деревья, когда структура dict больше подходит. Например, некорректно ссылаться на значение листа по индексу (child[1]), а также содержать имена узлов и дочерние элементы в одном и том же списке сомнительно (что приводит к итерации child[1:] для дочерних элементов, которая не является описательной). В хорошем коде python следует также избегать вызовов isinstance, но он нам нужен здесь, чтобы проверить, есть ли у нас лист.

В соответствии с передовой практикой листы должны быть узлами с None в качестве дочерних элементов. - это облегчает проверку состояния листа. Если мы реализуем то же самое с помощью dict of dicts и None дочерних элементов для листьев, функция очищает до:

def get_leaf_paths_dict(tree: dict, path=[], acc=[]):
    for node, children in tree.items():
        if children: # not leaf
            get_leaf_paths(children, path + [node], acc)
        else:
            acc.append((node, path))
    return acc

get_leaf_paths_2(tree)

, что намного приятнее для чтения. Для ясности, чтобы секунда работала, дерево должно быть заменено на dict dicts, ie:

{{'first':  {0: {'list1': None}, 
             1: {'list2': None}, 
             2: {'list3': None},
 {'second': { ... etc.

, и в качестве отступления, если вы строите свое дерево таким образом, вы можете импортировать его в Networkx с помощью функции nx.from_dict_of_dicts и выполните все манипуляции, которые API-интерфейс networkx дает вам оттуда.

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

Редактировать: я даже дам вам функцию для преобразования в диктовку бесплатных (обратите внимание на сходство):

def to_dict_of_dicts(tree, acc={}):
    for child in tree:
        if isinstance(child[1], list):
            acc[child[0]] = to_dict_of_dicts(child[1:])
        else:
            return {child[1] : None}
    return acc

print(to_dict_of_dicts(tree))