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

Question

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

Answer 1

Вы можете использовать этот алгоритм:

1. начать с корня и массива [1 ... m] в качестве массива параметров.
2. для каждой опции: выберите один и назначьтеroot
3. вызовите рекурсивный вызов после удаления этой опции для всех дочерних элементов

Возможно, этот псевдокод объяснит это лучше:

function assign(root, options) {
    for each options as option:
        assign root with option
        newOptions = options - option // remove newly assign value
        for each root->childs as child:
            call assign(child, newOptions) //recursive call after removing current option
} 

options = [1...m]
assign(root, options)

Это сложнее, чемметод грубой силы

Надеюсь, что поможет!