如何随机选择任意树的 N 节点子树。

Question

我有一个巨大的树形数据集。我正在尝试编写一个函数，该函数接受该树和一个数字N，并输出一个大小为N的随机树，该树包含较大树的根并被较大树包含，以便所有这样可能的子树（至少大致上）等可能地返回。较大树的平均节点具有数十个子节点，当N=1000时，该函数理想情况下不应该花费太长时间。这是否可能？

这篇论文在第8.2节中似乎恰好有这个问题，但我一个字也不懂。

我没有任何想法。我尝试查找现有文献并找到了答案，但如果它在那里，我就不明白它，我肯定不知道如何将解决方案转化为可工作的代码。每个明显的算法都要么不能均匀选择，要么需要滑稽的大量内存和运行时间。

- DrShitgenstein

---

我可以在有机会的时候编写该算法的实现，但我认为这不是你想要的。第一个问题是它会对任何大小的均匀子树进行采样，这意味着你必须运行该链直到它输出大小为N的子树（如果该大小很少见，则可能需要大量时间，正如你所说的那样）。第二个问题是，一般来说，它可能一开始就不能很快地混合 - 在最坏情况下，可能需要Omega(m^2)时间，其中m是原始树中节点的数量。我认为直接算法可能是你最好的选择。 - David Eisenstat

直接算法的时间复杂度应该是O(m N log N)，空间复杂度为O(m N)，但也有可能通过增加时间来减少内存使用。 - David Eisenstat

我能想到的算法需要创建一个具有O(m N)个条目的数据结构，其中m是大树的大小，而N是您想要的树的大小。每个条目都将是一个计算子树的大整数。这将占用大量内存。不过，您可以只存储每个数字的log。生成树的时间复杂度大约为O(N^2 b)，其中b是分支因子。这样做可以接受吗？ - btilly

可能某种近似方法会是最好的。您能解释一下为什么您想要在所有可能的子树中进行均匀选择吗？ - Matt Timmermans

Answer 1

通过过去的耦合抽样随机子树，如承诺所述。

import collections
import itertools
import random


# A tree is represented by a list mapping each node to its parent.
test_tree = [None, 0, 0, 2, 3, 3]


class AddNode:
    def __init__(self, u):
        self._u = u

    def __call__(self, tree, nodes):
        if tree[self._u] in nodes:
            nodes.add(self._u)


class DiscardNode:
    def __init__(self, u):
        self._u = u

    def __call__(self, tree, nodes):
        if all(tree[v] != self._u for v in nodes):
            nodes.discard(self._u)


# Coupling from the past.
def sample_subtree(tree):
    n = len(tree)
    T = 1
    steps = []
    while True:
        for t in range(T):
            steps.append(random.choice([AddNode, DiscardNode])(random.randrange(1, n)))
        upper = set(range(n))
        lower = {0}
        for step in reversed(steps):
            step(tree, upper)
            step(tree, lower)
        if upper == lower:
            return upper
        T *= 2


def is_subtree(tree, nodes):
    return all(node == 0 or tree[node] in nodes for node in nodes)


def test():
    n = len(test_tree)
    counter = collections.Counter()
    for i in range(100000):
        counter[frozenset(sample_subtree(test_tree))] += 1
    print(min(counter.values()) / max(counter.values()))
    assert all(is_subtree(test_tree, sub) for sub in counter)
    for k in range(1, n + 1):
        for comb in itertools.combinations(range(1, n), k):
            nodes = frozenset((0,) + comb)
            assert not is_subtree(test_tree, nodes) or nodes in counter


test()

- David Eisenstat