Possibili permutazioni dell'input di BST

Question

Mi viene assegnata una stringa, ad esempio "CPHBDZ". Inserendo (in questo ordine) le lettere a un BST avrò:

C 
/\ 
B P 
/\ 
    H Z 
/
D 

Se cambiamo fine della stringa a "CBPHDZ" Avremo albero identico. E devo trovare ed elencare tutte le permutazioni della stringa di input che forniscono la stessa BST. Mi è venuto in mente come calcolare un numero di queste permutazioni, ma non riesco a capire nessun algoritmo che le trovi effettivamente.

Answer 1

Supponendo che non si stia effettuando alcuna rotazione (ecc.) Per bilanciare l'albero, è possibile derivare una risposta dalla struttura dell'albero: i nuovi nodi vengono sempre aggiunti come discendenti di nodi esistenti, quindi qualsiasi nodo più in alto nel l'albero deve precedere la propria discendenza, ma può essere riorganizzato a piacimento con i suoi "pari" (tutto ciò che non è né il suo genitore né discendente).

Ad esempio, poiché la radice dell'albero è C, il C deve essere stato il primo elemento letto dallo stream. Poiché i suoi discendenti sono B e P, l'elemento successivo nell'input doveva essere uno di questi due. B non ha discendenti, ma P ha due: H e Z, quindi è necessario leggere dopo P, ma può essere in qualsiasi ordine rispetto a B. Allo stesso modo, Z può essere in qualsiasi ordine rispetto a H e D, ma H deve precedere D.

Modifica: per generare tutte quelle permutazioni, un modo semplice (imbroglio) sarebbe utilizzare Prolog. Fondamentalmente, codifichi tali dipendenze come "fatti" e genererà tutte le permutazioni che si adattano a questi fatti. In effetti (non è un gioco di parole), questa è praticamente una descrizione di ciò che Prolog fa/fa.

Facendolo da solo, probabilmente vorrai fare la maggior parte del lavoro in modo ricorsivo. Un ordine valido è una radice seguita da qualsiasi interleaving degli ordini validi dei suoi discendenti.

Per quanto riguarda l'interleaving, è necessario (ad esempio) generare un ordine valido del sottoalbero sinistro e un ordine valido della sottostruttura di destra. Mettili insieme in un array con tutti gli elementi del sottoalbero sinistro all'inizio e tutti quelli del sottoalbero destro alla fine. Per la dimostrazione, supponiamo che l'albero contenga anche un A (come discendente dello B che mostri). In un array, i nostri dati dal nostro sub-alberi sarà simile:

B A P H Z D 

Poi partiamo dall'ultima voce dal sotto-albero sinistro, e "camminare" ciascuna attraverso la matrice a destra, generando un nuova permutazione ogni volta:

B P A H Z D 
P B A H Z D 
B P H A Z D 
P B H A Z D 
P H B A Z D 
[ ... ]  

per ogni ordine valida del sub-struttura a sinistra, è necessario fare tutte queste interleavings con ogni ordine valida del diritto sub-albero (e restituirlo al genitore, che sarà Fai lo stesso).

Answer 2

In Python,

tree = { 
    'C' : ['B', 'P'], 
    'P' : ['H','Z'], 
    'H' : ['D']} 

def f(tree, ready): 
    if not ready: 
     return [[]] 
    else: 
     rv = [] 
     for r in ready: 
      for rest in f(tree, 
          [n for n in ready if r != n] + tree.get(r, [])): 
       rv.append([r] + rest) 
     return rv 

for o in f(tree, 'C'): 
    print ''.join(o)