Алгоритм перечисления уникальных способов удаления листьев с дерева?

Структура, которую вы должны ожидать, такова. Предположим, что у узла N есть дети C1, C2, ..., Cn. Также предположим, что options(node) — это количество способов удаления из node.

Тогда options(N) = options(C1) * options(C2) * ... * options(Cn) + 1. Почему? Первый термин заключается в том, что вы можете самостоятельно выбрать любой способ удаления ниже каждого дочернего элемента. И потом +1 потому что можно удалить всё поддерево, включая само N.

Чтобы их сгенерировать, просто переберите произведение вариантов для каждого дочернего элемента, а затем включите «все».

Вот решение для получения всех подмножеств. Я признаю, что мне не удалось использовать кеширование там, где я думал.

# A trivial tree implementation.
class Tree:
    def __init__ (self, label):
        self.label = label
        self.children = []

    def add_subtree (self, branch):
        self.children.append(branch)

    def all_labels (self):
        answer = [self.label]
        for child in self.children:
            answer = answer + child.all_labels()
        return answer

# We will be working with iter functions that:
#
#   - take an initial list of values.
#   - yield lists that start with that list of values.
#
# Here is a trivial example.
def empty_list_iter (initial):
    yield initial

# We will be doing higher order programming on these iter functions.
#
# That is, we will be using iter functions as data. This one gives
# all combinations from two iter functions. Each yielded list will
# have list a data followed by list b data.
def comb_iter_func (iter_func_a, iter_func_b):
    def comb_iter (initial):
        for next_initial in iter_func_a(initial):
            yield from iter_func_b(next_initial)
    return comb_iter

# Let's do the same for an arbitrary list of functions.
def product_iter_func (iter_funcs):
    if 0 == len(iter_funcs):
        # This is exactly analogous to an empty product returning 1.
        return empty_list_iter
    elif 1 == len(iter_funcs):
        return iter_funcs[0]
    else:
        # Recursively combine them.
        mid = len(iter_funcs) // 2
        return comb_iter_func(
                product_iter_func(iter_funcs[0:mid]),
                product_iter_func(iter_funcs[mid:]))

def removable_node_set_iter_func(tree):
    # This will iterate through all combinations of children.
    children_iter_func = product_iter_func(
            [removable_node_set_iter_func(child)
                for child in tree.children])

    # Here is the iter_func we will return.
    def this_iter (initial):
        # All things in the product of the children.
        yield from children_iter_func(initial)
        # The whole tree.
        yield initial + tree.all_labels()

    return this_iter

# Now our actual iter.
def removable_node_set_iter(tree):
    this_func = removable_node_set_iter_func(tree)
    yield from this_func([])

И вот быстрая проверка этого в действии.

# Now let's build a tree to test it on.
trees = [Tree(i) for i in range(6)]

# root 0. Children 1, 3. 2 is below 1. And 4,5 split below 3.
for parent, child in [(0, 1), (1, 2), (0, 3), (3, 4), (3, 5)]:
    trees[parent].add_subtree(trees[child])

for removable in removable_node_set_iter(trees[0]):
    print(removable)

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

Чтобы сгенерировать все поддеревья, включающие данный корень, вы должны взять все возможные подмножества его прямых дочерних элементов, то есть powerset его дочерних элементов, и для каждого дочернего элемента в одной такой комбинации вы решаете задачу рекурсивно, давая вам все возможные поддеревья. для этого ребенка. Примените декартово произведение к наборам поддеревьев, которые вы получили для каждого дочернего элемента в данной комбинации, чтобы построить одно уникальное поддерево (добавив корень).

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

Ниже две реализации:

1. Реализация JavaScript

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

class Node {
    constructor(value, ...children) {
        this.value = value;
        this.children = children;
    }
}

// Produce all subsets of given unique values
function* powerset(arr) {
    if (arr.length == 0) {
        yield [];
    } else {
        for (const subseq of powerset(arr.slice(1))) {
            yield subseq;
            yield [arr[0], ...subseq];
        }
    }
}

// Produce Cartesian product of given arrays
function* product(arrays) {
    if (arrays.length == 0) {
        yield [];
    } else {
        for (const rest of product(arrays.slice(1))) {
            for (const item of arrays[0]) {
                yield [item, ...rest];
            }
        }
    }
}

// Get the flattened elements from the given arrays
function* flatten(arrays) {
    for (const item of arrays) yield item.flat();
}

// Main algorithm: generate all possible, non-empty subtrees with given root
function* allSubtreeValues(root) {
    yield [root.value];
    for (const childSelection of powerset(root.children)) {
        const subtrees = childSelection.map(child => Array.from(allSubtreeValues(child)));
        for (const selected of flatten(product(subtrees))) {
            if (selected.length) yield [root.value, ...selected];
        }
    }
}

// Gets all values present in a given tree
function* allValues(root) {
    if (!root) return;
    yield root.value;
    for (const child of root.children) yield* allValues(child);
}

// Subtracts values from a given array with unique values.
function difference(a, b) {
    const exclude = new Set(b);
    return a.filter(val => !exclude.has(val));
}

// Function that gets the complementary values from allSubtreeValues()
function* allLeafPluckSets(root) {
    const all = Array.from(allValues(root));
    yield all;
    for (const subtreeValues of allSubtreeValues(root)) {
        yield difference(all, subtreeValues);
    }
}

// Demo
console.info("Example 1:");
const root = // continues below...
new Node(1,
    new Node(2, 
        new Node(4)
    ),
    new Node(3, 
        new Node(5)
    )
);
for (const values of allLeafPluckSets(root)) 
    console.info(JSON.stringify(values));

console.info("Example 2:");
const root2 = // continues below...
new Node(1,
    new Node(2, 
        new Node(3,
            new Node(4), 
            new Node(5)
        )
    )
);
for (const values of allLeafPluckSets(root2)) 
    console.info(JSON.stringify(values));

2. Реализация Python

Вот аналогичная реализация, но на Python с использованием некоторых функций itertools и more_itertools:

from itertools import product
from more_itertools import powerset, flatten

class Node:
    def __init__(self, value, *children):
        self.value = value
        self.children = children

# Get all the values in the given tree
def all_values(root):
    if root:
        yield root.value
        for child in root.children:
            yield from all_values(child)

# Main algorithm: get all possible subtrees (their values) with this root
def all_subtree_values(root):
    yield [root.value]
    for child_selection in powerset(root.children):
        subtrees = [
            list(all_subtree_values(child))
            for child in child_selection
        ]
        for selected in product(*subtrees):
            if selected:
                yield [root.value, *flatten(selected)]

# Get all the subtrees, but now produce the values NOT in a subtree
def all_leaf_pluck_sets(root):
    values = set(all_values(root))
    yield values
    for subtreeValues in all_subtree_values(root):
        yield values.difference(subtreeValues)

Пример использования:

# Example 1
root = Node(1,
    Node(2, 
        Node(4)
    ),
    Node(3, 
        Node(5)
    )
)
for values in all_leaf_pluck_sets(root):
    print(values)

# Example 2
root = Node(1,
    Node(2, 
        Node(3,
            Node(4), 
            Node(5)
        )
    )
)
for values in all_leaf_pluck_sets(root):
    print(values)