permutaciones de BST

Question

Dada una matriz de enteros arr = [5,6,1].

Cuando construimos un BST con esta entrada en el mismo orden, tendremos "5" como raíz, "6" como el hijo derecho y "1" como hijo izquierdo.

Ahora si nuestra entrada se cambia a [5,1,6], nuestra estructura BST seguirá siendo idéntica.

Por lo tanto, dado un conjunto de enteros, ¿cómo encontrar el número de permutaciones diferentes de la matriz de entrada que da como resultado la BST idéntica a la BST formada en el orden de matriz original?

Answer 1

Usted puede hacer esto al revés: Dado un BST, enumerar todos los conjuntos de números enteros que podrían producir este BST ...

No podría usted (usando determinismo ...)

1. emiten rootear y agregarlo al conjunto emitido.
2. no deterministically elegir un elemento del árbol que no está en el conjunto emitido, pero cuyo principal es, y agregarlo al conjunto emitido y emitirlo.
3. repite 2 hasta que se emita todo.

El nondeterminism le dará todas esas matrices. Entonces puedes contarlos.

Answer 2

Su pregunta es equivalente a la cuestión de contar el número de ordenamientos topológicos para la BST dada.

Por ejemplo, para la BST

10 
/\ 
5 20 
\7 | \ 
    15 30 

el conjunto de ordenaciones topológicos se puede contar con la mano de esta manera: 10 aperturas cada pedido. El número de ordenamientos topológicos para el subárbol que comienza con 20 es dos: (20, 15, 30) y (20, 30, 15). El subárbol que comienza con 5 tiene solo un orden: (5, 7). Estas dos secuencias se pueden intercalar de manera arbitraria, lo que lleva a intercalaciones de 2 x 10, produciendo así veinte entradas que producen la misma BST. El primero 10 se enumeran a continuación para el 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 

El caso (20, 30, 15) es análoga --- se puede comprobar que cualquiera de las siguientes entradas produce la mismo BST.

Este ejemplo también proporciona una regla recursiva para calcular el número de ordenamientos. Para una hoja, el número es 1. Para un nodo no hoja con un hijo, el número es igual al número de ordenamientos topológicos para el niño. Para un nodo no hoja con dos hijos con tamaños de subárbol | L | y | R |., ambos con L y R ordenamientos, resp, el número es igual a

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

Dónde INT es el número de posibles intercalaciones de | L | y | R | elementos. Esto se puede calcular fácilmente por (| L | + | R |)!/(| L |! X | R |!). Para el ejemplo anterior, obtenemos el siguiente cálculo recursivo:

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 

Esto soluciona el problema.

Nota: esta solución asume que todos los nodos en el BST tienen claves diferentes.

Answer 3

Gracias por la explicación antti.huima! Esto me ayudó a entender. Aquí hay alguna 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

Esta cuestión puede resolverse fácilmente si se tiene poco conocimiento de la repetición, permutaciones y combinaciones, y la familiaridad con el árbol de búsqueda binaria (obviamente).

Primero construye un árbol de búsqueda binaria con la secuencia dada. También puede realizar la misma operación en la matriz, pero la visualización de árbol daría una buena imagen.

Para la secuencia dada arr [1..n], el primer elemento se mantendría como está en la matriz dada y solo se debe presentar la disposición en arr [2..n].

Supongamos:

bag1 = número de elementos de matriz [2..n] que son menos de arr [0].

y,

bag2 = número de elementos de matriz [2..n] que son mayores que arr [0].

Dado que la permutación de los elementos en bag1 en la secuencia no entrará en conflicto con los números presentes en la bolsa2 mientras se forma un árbol de búsqueda binaria, uno puede comenzar a calcular la respuesta por -1) elementos para permutar y luego resto ((n-1) - bag1) = elementos bag2 se pueden colocar de 1 manera solo ahora. El orden de los elementos en bag1 debería ser el mismo y también para los elementos de bag2 en la secuencia.

Dado que cada subárbol de un árbol de búsqueda binario tiene que ser una BST. Se operará un proceso similar en cada nodo y se multiplicará la respuesta local para el nodo a la respuesta final.

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