Itération uniformément aléatoire des sous-arbres

Question

Je veux itérer le premier $ k $ Éléments d'une liste ordonnée au hasard contenant tous les sous-arbres pour un arbre donné. La définition des sous-arbres que j'utilise est: "Un sous-arbre de $ T $ est un sous-graphique de $ T $ c'est aussi un arbre ". Par exemple, un arbre $ A (b (d, e, f), c (g, h)) $ devrait avoir 62 sous-arbres si mes mathématiques sont correctes.

La quantité de sous-arbres peut être calculée comme suit. Désignons $ R (t) $ le nombre de sous-arbres de $ T $ enraciné $ T $. Si $ T $ est une feuille alors $ R (t) = 1 $, et si l'arbre a des enfants $ T_1, ldots, t_ ell $ alors$$ r (t) = prod_ {i = 1} ^ ell (r (t_i) + 1). $$Enfin, le nombre de sous-arbres de $ T $ est $ sum_ {x in t} r (t_x) $, où $ x $ passe sur tous les sommets de $ T $, et $ T_x $ le sous-arbre est-il induit par $ x $ (composé de $ x $ et toute sa progéniture).

En mélangeant l'ordre de ces arbres et en répertoriant les 5 premiers, le résultat pourrait être $ C (g), a (b (f)), b (d, e), a (b, c), c $.

Je peux déjà générer une liste complète de sous-arbres. Pour les plus grands arbres, cela devient rapidement incroyablement grand. Je cherche un moyen de générer ces sous-arbres sans avoir à les générer tous.

Une méthode possible à laquelle j'ai pensé est de garder un compte du nombre de sous-arbres enracinés invisibles que chacun des nœuds a laissé, et décrémentant chaque fois qu'un sous-arbre est généré à partir de ce nœud. La probabilité qu'un nœud soit sélectionné serait pondéré par ce compteur. Je devrais également empêcher la génération de doublons. Je me demandais s'il y avait une meilleure façon.