permutacje BST

Question

Biorąc pod uwagę tablicę liczb całkowitych arr = [5,6,1].

Kiedy skonstruujemy BST z tym wejściem w tej samej kolejności, będziemy mieć "5" jako root, "6" jako prawe dziecko i "1" jako lewe dziecko.

Teraz, jeśli nasze dane wejściowe zostaną zmienione na [5,1,6], nadal nasza struktura BST będzie identyczna.

Tak więc biorąc pod uwagę tablicę liczb całkowitych, jak znaleźć liczbę różnych permutacji tablicy wejściowej, która powoduje identyczne BST, jak BST utworzony w oryginalnej kolejności macierzy?

Answer 1

Można to zrobić w tył: Biorąc pod uwagę BST, wyliczyć wszystkie tablice liczb całkowitych, które mogłyby dają ten BST ...

nie mógłbyś (używając nondeterminism ...)

1. Emit root i dodaj go do emitowanego zestawu.
2. niedeterministycznie wybierz element z drzewa, który nie znajduje się w emitowanym zbiorze, , ale którego rodzic jest i dodaj go do emitowanego zestawu i wyślij go.
3. Powtórz 2 aż wszystkie zostaną wydane.

Niedeterminizm da ci wszystkie takie tablice. Wtedy możesz je policzyć.

Answer 2

Twoje pytanie jest równoznaczne z zliczaniem liczby porządków topologicznych dla danego BST.

Na przykład, dla BST

10 
/\ 
5 20 
\7 | \ 
    15 30 

zestawu porządków topologicznych można policzyć ręcznie tak: 10 rozpoczyna każdy zamówieniu. Liczba porządków topologicznych dla poddrzewa rozpoczynającego się od 20 to dwa: (20, 15, 30) i (20, 30, 15). Subtree zaczynający się od 5 ma tylko jedną kolejność: (5, 7). Te dwie sekwencje mogą być przeplatane w dowolny sposób, prowadząc do 2 x 10 przeplotów, wytwarzając w ten sposób dwadzieścia danych wejściowych, które wytwarzają ten sam BST. Pierwszy 10 są wymienione poniżej dla przypadku (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 

obudowy (20, 30, 15) jest analogiczna --- można sprawdzić, że każdy z następujących wejść produkuje ten sam BST.

W przykładach podano również regułę rekurencyjną do obliczania liczby zamówień. Dla liścia liczba wynosi 1. Dla węzła innego niż liść z jednym dzieckiem liczba jest równa liczbie porządków topologicznych dla dziecka. Dla węzła bez liści z dwójką dzieci o rozmiarach poddrzewa | L | i | r |., oba posiadające uporządkowania L i R, odpowiednio, liczba równa

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

gdzie INT jest liczbą możliwych interleavings o | l | i | R | elementy. Można to łatwo obliczyć przy pomocy (| L | + | R |)!/(| L |! X | R |!). W powyższym przykładzie otrzymujemy następujące obliczenia rekurencyjne:

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 

Rozwiązuje to problem.

Uwaga: to rozwiązanie zakłada, że ​​wszystkie węzły w BST mają różne klucze.

Answer 3

Dzięki za wyjaśnienie antti.huima! To pomogło mi zrozumieć. Oto niektóre 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

to pytanie można łatwo rozwiązać, jeśli masz trochę wiedzy rekursji, permutacji i kombinacji oraz znajomości binarne drzewo poszukiwań (oczywiście).

Najpierw należy zbudować drzewo wyszukiwania binarnego z podaną sekwencją. Możesz także wykonać tę samą operację w macierzy, ale wizualizacja drzewa pomaluje dobre zdjęcie.

Dla podanej sekwencji arr [1..n], pierwszy element pozostanie ustawiony tak, jak jest w podanej macierzy i tylko aranżacja musi zostać wprowadzona w arr [2..n].

Załóżmy:

bag1 = liczba elementów arr [2..n], które są mniejsze niż ARR [0].

i

bag2 = liczba elementów arr [2..n], które są większe niż ARR [0].

Ponieważ permutacja elementów w worku 1 w sekwencji nie spowoduje konfliktu z liczbami obecnymi w worku2 podczas tworzenia binarnego drzewa wyszukiwania, można zacząć obliczać odpowiedź przez wybierając elementy bag1 z (n -1) elementy do permutacji i , a następnie spoczynku ((n-1) - worek1) = elementy bag2 mogą być teraz umieszczone tylko w jeden sposób teraz. Kolejność elementów w worku 1 powinna być taka sama i podobnie dla elementów worka 2 w sekwencji.

Ponieważ każde poddrzewo drzewa wyszukiwania binarnego musi być BST. Podobny proces będzie działał na każdym węźle i mnoży odpowiedź lokalną dla węzła do ostatecznej odpowiedzi.

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; 
}