Iterazione uniformemente casuale dei sottotei

Question

Voglio iterare attraverso il primo $ k $ Elementi di un elenco ordinato in modo casuale contenente tutti i subtrees per un determinato albero. La definizione di sottostruttura che sto usando è: "Una sottostruttura di $ T $ è un sottografo di $ T $ Questo è anche un albero ". Ad esempio, un albero $ A (b (d, e, f), c (g, h)) $ Dovrei avere 62 subtrees se la mia matematica è corretta.

La quantità di sottostruttura può essere calcolata come segue. Indichiamo da $ R (t) $ il numero di sottostrutture di $ T $ radicato a $ T $. Se $ T $ è una foglia allora $ R (t) = 1 $, e se l'albero ha figli $ T_1, ldots, t_ ell $ poi$$ r (t) = prod_ {i = 1}^ ell (r (t_i) + 1). $$Infine, il numero di sottostrutture di $ T $ è $ sum_ {x in t} r (t_x) $, dove $ x $ va oltre tutti i vertici di $ T $, e $ T_x $ è il sottostruttura indotta da $ x $ (consiste in $ x $ e tutta la sua progenie).

Sposchiando l'ordine di questi alberi ed elencando i primi 5, il risultato potrebbe essere $ C (g), a (b (f)), b (d, e), a (b, c), c $.

Posso già generare un elenco completo di sottostrutimenti. Per gli alberi più grandi, questo diventa rapidamente incredibilmente grande. Sto cercando un modo per generare questi sottosuolo senza doverli generare tutti.

Un possibile metodo a cui ho pensato è di mantenere un conteggio di quanti sottocreti invisibili hanno lasciato ciascuno dei nodi e diminuendo ogni volta che una sottostruttura viene generata da quel nodo. La probabilità che venga selezionato un nodo verrebbe ponderata da questo contatore. Dovrei anche prevenire la generazione di duplicati. Mi chiedevo se esistesse un modo migliore.