Создать случайный граф дерева из известных вершин для каждого поколения

Question

У меня есть список, например [2, 5, 9]. Каждый индекс представляет количество вершин в каждом поколении. Например, в поколении 0 есть 2 узла. Эти 2 узла имеют 5 детей, 5 детей - 9 детей и т.д. c. Из этого я хочу иметь возможность генерировать древовидный граф, но там, где у детей есть случайные родители. Я также хочу установить максимальное количество детей, которое может иметь один узел. Так, например, поколение 1 не может превышать 6 узлов, поскольку в этом поколении есть 2 родителя, и у каждого родителя может быть только 3 ребенка.

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

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

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

levels = [2, 5, 9]
arr = [[] for i in range(levels[0])]
for i in range(1, len(levels)-1):
    level = levels[i]
    while(level > 0):
        j = random.randint(0, levels[i-1]-1)
        arr[j].append([])
        level -= 1

Что печатает эти списки (в случайном порядке)

[[[]], [[], [], [], []]]
[[[], [], []], [[], []]]
[[[], []], [[], [], []]]

Это в конечном итоге то, что я хочу, но это правильное решение для [2, 5], а не [2, 5, 9 ]. Я не знаю, как go перейти к следующему поколению отсюда. Я застрял в этом в течение некоторого времени, и я пытался использовать рекурсивную функцию, но с небольшим успехом (как правило, список индекса из-за ошибок диапазона).

Я хотел бы спросить, есть ли лучший способ для генерации такого дерева из этого списка начальной генерации [2, 5, 9], и есть ли лучший способ для представления деревьев в целом ... Желательно без используя класс дерева. Спасибо за помощь.

Answer 1

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

import random
import json

max_children_per_parent = 3


def assign_parents(trees, parents):
    if len(trees) > len(parents) * max_children_per_parent:
        raise ValueError

    for tree in trees:
        while True:
            parent = random.choice(parents)
            if len(parent) < max_children_per_parent:
                parent.append(tree)
                break


def generate_tree_bottom_up(levels):
    bottom = [[] for _ in range(levels[-1])]
    for level in reversed(levels[:-1]):
        parents = [[] for _ in range(level)]
        assign_parents(bottom, parents)
        bottom = parents
    return bottom


def generate_tree_top_down(levels):
    root = top = [[] for _ in range(levels[0])]
    for level in levels[1:]:
        children = [[] for _ in range(level)]
        assign_parents(children, top)
        top = children
    return root


def main():
    for method in [generate_tree_bottom_up, generate_tree_top_down]:
        print(json.dumps(method([2, 5, 9]), indent=4))


if __name__ == '__main__':
    main()

Вывод:

[
    [
        [
            [],
            []
        ],
        [
            [],
            [],
            []
        ]
    ],
    [
        [
            [],
            []
        ],
        [
            []
        ],
        [
            []
        ]
    ]
]
[
    [
        [
            []
        ],
        [
            [],
            [],
            []
        ]
    ],
    [
        [
            [],
            []
        ],
        [
            [],
            [],
            []
        ],
        []
    ]
]

Список - это естественный способ представления переменного числа объектов, включая дочерние, поэтому ты не собираешься уходить от них. Если это не просто списки, это будет какой-то класс дерева, содержащий списки. Но вы можете найти способы более удобного просмотра представления, например json.dumps(..., indent=4).