permutazioni di BST

Question

Dato un array di interi arr = [5,6,1].

Quando costruiamo un BST con questo input nello stesso ordine, avremo "5" come root, "6" come figlio destro e "1" come figlio sinistro.

Ora, se il nostro input viene modificato in [5,1,6], la nostra struttura BST sarà identica.

Quindi, dato un array di numeri interi, come trovare il numero di diverse permutazioni dell'array di input che risulta nell'identico BST come il BST formato nell'ordine originale dell'array?

Answer 1

Si potrebbe fare questo a ritroso: Dato un BST, enumerare tutti gli array di interi che potrebbe produrre questa BST ...

Impossibile voi (usando nondeterminismo ...)

1. Emit root e aggiungerlo al set emesso.
2. scegliere in modo non deterministico un elemento dall'albero che non si trova nel set emesso, ma di cui è padre e aggiungerlo al set emesso ed emetterlo.
3. ripetere 2 fino a quando tutti emessi.

Il nondeterminismo vi darà tutti questi array. Quindi puoi contarli.

Answer 2

La domanda è equivalente alla domanda di conteggio del numero di ordini topologici per la data BST.

Ad esempio, per il BST

10 
/\ 
5 20 
\7 | \ 
    15 30 

l'insieme di ordinamenti topologici possono contare a mano come questo: 10 inizia ogni ordinazione. Il numero di ordini topologici per la sottostruttura che inizia con 20 è due: (20, 15, 30) e (20, 30, 15). La sottostruttura che inizia con 5 ha solo un ordine: (5, 7). Queste due sequenze possono essere intercalate in modo arbitrario, portando a 2 x 10 interlacciamenti, producendo quindi venti ingressi che producono la stessa BST. Il primo 10 sono elencati di seguito per il caso (20, 15, 30):

10 5 7 20 15 30 
10 5 20 7 15 30 
10 5 20 15 7 30 
10 5 20 15 30 7 
10 20 5 7 15 30 
10 20 5 15 7 30 
10 20 5 15 30 7 
10 20 15 5 7 30 
10 20 15 5 30 7 
10 20 15 30 5 7 

il caso (20, 30, 15) è analogo --- è possibile verificare che uno qualsiasi dei seguenti ingressi produce la stessa BST.

Questo esempio fornisce anche una regola ricorsiva per calcolare il numero degli ordini. Per una foglia, il numero è 1. Per un nodo non foglia con un figlio, il numero è uguale al numero di ordini topologici per il bambino. Per un nodo non foglia con due bambini con dimensioni di sottostruttura | L | e | R |., entrambi con L e R ordinamenti, risp, il numero è uguale a

l x r x INT(|L|, |R|) 

Dove INT è il numero di possibili interleavings di | L | e | R | elementi. Questo può essere calcolato facilmente da (| L | + | R |)!/(| L |! X | R |!). Per l'esempio precedente, otteniamo il seguente calcolo ricorsivo:

Ord(15) = 1 
    Ord(30) = 1 
    Ord(20) = 1 x 1 x INT(1, 1) = 2 ; INT(1, 1) = 2!/1 = 2 
    Ord(7) = 1 
    Ord(5) = 1 
    Ord(10) = 1 x 2 x INT(2, 3) = 2 x 5!/(2! x 3!) = 2 x 120/12 = 2 x 10 = 20 

Questo risolve il problema.

Nota: questa soluzione presuppone che tutti i nodi nel BST dispongano di chiavi diverse.

Answer 3

Grazie per la spiegazione antti.huima! Questo mi ha aiutato a capire. Ecco qualche C++:

#include <vector> 
#include <iostream> 

using namespace std; 

int factorial(int x) { 
    return (x <= 1) ? 1 : x * factorial(x - 1); 
} 

int f(int a, int b) { 
    return factorial(a + b)/(factorial(a) * factorial(b)); 
} 

template <typename T> 
int n(vector<T>& P) { 
    if (P.size() <= 1) return 1; 
    vector<T> L, R; 
    for (int i = 1; i < P.size(); i++) { 
    if (P[i] < P[0]) 
     L.push_back(P[i]); 
    else 
     R.push_back(P[i]); 
    } 
    return n(L) * n(R) * f(L.size(), R.size()); 
} 

int main(int argc, char *argv[]) { 
    vector<int> a = { 10, 5, 7, 20, 15, 30 }; 
    cout << n(a) << endl; 
    return 0; 
} 

Answer 4

Questa domanda può essere risolto facilmente se si ha poca conoscenza di ricorsione, permutazione e le combinazioni, e la familiarità con Binary Search Albero (ovviamente).

Per prima cosa si costruisce un albero di ricerca binario con la sequenza indicata. È anche possibile eseguire la stessa operazione nell'array ma la visualizzazione ad albero dipingerebbe una buona immagine.

Per la sequenza data arr [1..n], il primo elemento rimane inserito come è nell'array dato e solo l'arrangiamento deve essere inserito in arr [2..n].

assumere:

bag1 = numero di elementi arr [2..n] che sono meno di arr [0].

e,

bag2 = numero di elementi arr [2..n] che sono superiori arr [0].

Poiché la permutazione degli elementi nel bag1 nella sequenza non porrà un conflitto con i numeri presenti nel bag2 mentre forma un albero di ricerca binario, si può iniziare a calcolare la risposta con prelevando elementi bag1 da (n -1) elementi per permutare e quindi riposare ((n-1) - bag1) = gli elementi bag2 possono essere collocati in 1 modo solo ora. L'ordine degli elementi nel bag1 dovrebbe essere lo stesso e anche per gli elementi bag2 nella sequenza.

Poiché ciascun sottoalbero di un albero di ricerca binario deve essere un BST. Un processo simile verrebbe gestito su ciascun nodo e moltiplica la risposta locale per il nodo alla risposta finale.

int ans = 1; 
int size[1000000] = {0}; 

// calculate the size of tree and its subtrees before running function "fun" given below. 
int calSize(struct node* root){ 
    if(root == NULL) 
      return 0; 

    int l = calSize(root->left); 
    int r = calSize(root -> right); 
    size[root->val] = l+r+1; 
    return size[root->val]; 
} 

void fun(struct node* root){ 
    if(root == NULL) 
     return; 

    int n = size[root->val]; 
    if(root->left){ 
     ans *= nCr(n-1, size[root->left]); 
     ans *= 1; // (Just to understand that there is now only 1 way 
        //to distribute the rest (n-1)-size of root->left) 
    } 

    fun(root->left); 
    fun(root->right); 
} 

int main(){ 
    struct node* root; 

    //construct tree 
    //and send the root to function "fun" 

    fun(root); 

    cout<<ans<<endl; 
    return 0; 
}