Cuente las permutaciones de una array dada que genera el mismo árbol de búsqueda binaria (BST)

Posted on by Rudeus Greyrat

Dada una array , arr[] de tamaño N que consta de elementos del rango [1, N] , que representa el orden en que los elementos se insertan en un árbol de búsqueda binario , la tarea es contar el número de formas de reorganizar la array dada para obtener el mismo BST .

Ejemplos:

Entrada: arr[ ] ={3, 4, 5, 1, 2}
Salida: 6
Explicación:
las permutaciones de la array que representan el mismo BST son: {{3, 4, 5, 1, 2}, {3, 1, 2, 4, 5}, {3, 1, 4, 2, 5}, {3, 1, 4, 5, 2}, {3, 4, 1, 2, 5}, {3, 4, 1, 5, 2}}. Por lo tanto, la salida es 6.

Entrada:  arr[ ] ={2, 1, 6, 5, 4, 3}
Salida: 5

Enfoque: la idea es arreglar primero el Node raíz y luego contar recursivamente el número de formas de reorganizar los elementos del subárbol izquierdo y los elementos del subárbol derecho de tal manera que el orden relativo dentro de los elementos del subárbol izquierdo y el subárbol derecho debe ser el mismo. Aquí está la relación de recurrencia:

contarVías(arr) = contarVías(izquierda) * contarVías(derecha) * combinaciones(N, X).
izquierda: Contiene todos los elementos del subárbol izquierdo (Elementos que son menores que la raíz) 
derecha: Contiene todos los elementos del subárbol derecho (Elementos que son mayores que la raíz) 
N = Número total de elementos en arr[] 
X = Número total de elementos en el subárbol izquierdo.

Siga los pasos a continuación para resolver el problema:

  1. Repare el Node raíz de BST y almacene los elementos del subárbol izquierdo (Elementos que son menores que arr[0]), diga ctLeft[] y almacene los elementos del subárbol derecho (Elementos que son mayores que arr[0] ), diga ctRight[].
  2. Para generar BST idénticos, mantenga el orden relativo dentro de los elementos del subárbol izquierdo y el subárbol derecho.
  3. Calcule la cantidad de formas de reorganizar la array para generar BST utilizando la relación de recurrencia mencionada anteriormente.

C++

// C++ program to implement
// the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to precompute the
// factorial of 1 to N
void calculateFact(int fact[], int N)
{
    fact[0] = 1;
    for (long long int i = 1; i < N; i++) {
        fact[i] = fact[i - 1] * i;
    }
}
 
// Function to get the value of nCr
int nCr(int fact[], int N, int R)
{
    if (R > N)
        return 0;
 
    // nCr= fact(n)/(fact(r)*fact(n-r))
    int res = fact[N] / fact[R];
    res /= fact[N - R];
 
    return res;
}
 
// Function to count the number of ways
// to rearrange the array to obtain same BST
int countWays(vector<int>& arr, int fact[])
{
    // Store the size of the array
    int N = arr.size();
 
    // Base case
    if (N <= 2) {
        return 1;
    }
 
    // Store the elements of the
    // left subtree of BST
    vector<int> leftSubTree;
 
    // Store the elements of the
    // right subtree of BST
    vector<int> rightSubTree;
 
    // Store the root node
    int root = arr[0];
 
    for (int i = 1; i < N; i++) {
 
        // Push all the elements
        // of the left subtree
        if (arr[i] < root) {
            leftSubTree.push_back(
                arr[i]);
        }
 
        // Push all the elements
        // of the right subtree
        else {
            rightSubTree.push_back(
                arr[i]);
        }
    }
 
    // Store the size of leftSubTree
    int N1 = leftSubTree.size();
 
    // Store the size of rightSubTree
    int N2 = rightSubTree.size();
 
    // Recurrence relation
    int countLeft
        = countWays(leftSubTree,
                    fact);
    int countRight
        = countWays(rightSubTree,
                    fact);
 
    return nCr(fact, N - 1, N1)
           * countLeft * countRight;
}
 
// Driver Code
int main()
{
 
    vector<int> arr;
    arr = { 3, 4, 5, 1, 2 };
 
    // Store the size of arr
    int N = arr.size();
 
    // Store the factorial up to N
    int fact[N];
 
    // Precompute the factorial up to N
    calculateFact(fact, N);
 
    cout << countWays(arr, fact);
 
    return 0;
}

Java

// Java program to implement
// the above approach
import java.util.*;
 
class GFG{
 
// Function to precompute the
// factorial of 1 to N
static void calculateFact(int fact[], int N)
{
    fact[0] = 1;
    for(int i = 1; i < N; i++)
    {
        fact[i] = fact[i - 1] * i;
    }
}
 
// Function to get the value of nCr
static int nCr(int fact[], int N, int R)
{
    if (R > N)
        return 0;
 
    // nCr= fact(n)/(fact(r)*fact(n-r))
    int res = fact[N] / fact[R];
    res /= fact[N - R];
 
    return res;
}
 
// Function to count the number of ways
// to rearrange the array to obtain same BST
static int countWays(Vector<Integer> arr,
                     int fact[])
{
     
    // Store the size of the array
    int N = arr.size();
 
    // Base case
    if (N <= 2)
    {
        return 1;
    }
 
    // Store the elements of the
    // left subtree of BST
    Vector<Integer> leftSubTree = new Vector<Integer>();
 
    // Store the elements of the
    // right subtree of BST
    Vector<Integer> rightSubTree = new Vector<Integer>();
 
    // Store the root node
    int root = arr.get(0);
 
    for(int i = 1; i < N; i++)
    {
         
        // Push all the elements
        // of the left subtree
        if (arr.get(i) < root)
        {
            leftSubTree.add(arr.get(i));
        }
 
        // Push all the elements
        // of the right subtree
        else
        {
            rightSubTree.add(arr.get(i));
        }
    }
 
    // Store the size of leftSubTree
    int N1 = leftSubTree.size();
 
    // Store the size of rightSubTree
    int N2 = rightSubTree.size();
 
    // Recurrence relation
    int countLeft = countWays(leftSubTree,
                              fact);
    int countRight = countWays(rightSubTree,
                               fact);
 
    return nCr(fact, N - 1, N1) *
             countLeft * countRight;
}
 
// Driver Code
public static void main(String[] args)
{
    int []a = { 3, 4, 5, 1, 2 };
     
    Vector<Integer> arr = new Vector<Integer>();
    for(int i : a)
        arr.add(i);
         
    // Store the size of arr
    int N = a.length;
 
    // Store the factorial up to N
    int []fact = new int[N];
 
    // Precompute the factorial up to N
    calculateFact(fact, N);
 
    System.out.print(countWays(arr, fact));
}
}
 
// This code is contributed by Amit Katiyar

Python3

# Python3 program to implement
# the above approach
 
# Function to precompute the
# factorial of 1 to N
def calculateFact(fact: list, N: int) -> None:
 
    fact[0] = 1
    for i in range(1, N):
        fact[i] = fact[i - 1] * i
 
# Function to get the value of nCr
def nCr(fact: list, N: int, R: int) -> int:
 
    if (R > N):
        return 0
 
    # nCr= fact(n)/(fact(r)*fact(n-r))
    res = fact[N] // fact[R]
    res //= fact[N - R]
 
    return res
 
# Function to count the number of ways
# to rearrange the array to obtain same BST
def countWays(arr: list, fact: list) -> int:
 
    # Store the size of the array
    N = len(arr)
 
    # Base case
    if (N <= 2):
        return 1
 
    # Store the elements of the
    # left subtree of BST
    leftSubTree = []
 
    # Store the elements of the
    # right subtree of BST
    rightSubTree = []
 
    # Store the root node
    root = arr[0]
 
    for i in range(1, N):
 
        # Push all the elements
        # of the left subtree
        if (arr[i] < root):
            leftSubTree.append(arr[i])
 
        # Push all the elements
        # of the right subtree
        else:
            rightSubTree.append(arr[i])
 
    # Store the size of leftSubTree
    N1 = len(leftSubTree)
 
    # Store the size of rightSubTree
    N2 = len(rightSubTree)
 
    # Recurrence relation
    countLeft = countWays(leftSubTree, fact)
    countRight = countWays(rightSubTree, fact)
 
    return (nCr(fact, N - 1, N1) *
            countLeft * countRight)
 
# Driver Code
if __name__ == '__main__':
 
    arr = [ 3, 4, 5, 1, 2 ]
 
    # Store the size of arr
    N = len(arr)
 
    # Store the factorial up to N
    fact = [0] * N
 
    # Precompute the factorial up to N
    calculateFact(fact, N)
     
    print(countWays(arr, fact))
 
# This code is contributed by sanjeev2552

C#

// C# program to implement
// the above approach
using System;
using System.Collections.Generic;
 
class GFG{
 
// Function to precompute the
// factorial of 1 to N
static void calculateFact(int []fact, int N)
{
    fact[0] = 1;
    for(int i = 1; i < N; i++)
    {
        fact[i] = fact[i - 1] * i;
    }
}
 
// Function to get the value of nCr
static int nCr(int []fact, int N, int R)
{
    if (R > N)
        return 0;
 
    // nCr= fact(n)/(fact(r)*fact(n-r))
    int res = fact[N] / fact[R];
    res /= fact[N - R];
 
    return res;
}
 
// Function to count the number of ways
// to rearrange the array to obtain same BST
static int countWays(List<int> arr,
                     int []fact)
{
     
    // Store the size of the array
    int N = arr.Count;
 
    // Base case
    if (N <= 2)
    {
        return 1;
    }
 
    // Store the elements of the
    // left subtree of BST
    List<int> leftSubTree = new List<int>();
 
    // Store the elements of the
    // right subtree of BST
    List<int> rightSubTree = new List<int>();
 
    // Store the root node
    int root = arr[0];
 
    for(int i = 1; i < N; i++)
    {
         
        // Push all the elements
        // of the left subtree
        if (arr[i] < root)
        {
            leftSubTree.Add(arr[i]);
        }
 
        // Push all the elements
        // of the right subtree
        else
        {
            rightSubTree.Add(arr[i]);
        }
    }
 
    // Store the size of leftSubTree
    int N1 = leftSubTree.Count;
 
    // Store the size of rightSubTree
    int N2 = rightSubTree.Count;
 
    // Recurrence relation
    int countLeft = countWays(leftSubTree,
                              fact);
    int countRight = countWays(rightSubTree,
                               fact);
 
    return nCr(fact, N - 1, N1) *
             countLeft * countRight;
}
 
// Driver Code
public static void Main(String[] args)
{
    int []a = { 3, 4, 5, 1, 2 };
     
    List<int> arr = new List<int>();
    foreach(int i in a)
        arr.Add(i);
         
    // Store the size of arr
    int N = a.Length;
 
    // Store the factorial up to N
    int []fact = new int[N];
 
    // Precompute the factorial up to N
    calculateFact(fact, N);
 
    Console.Write(countWays(arr, fact));
}
}
 
// This code is contributed by Amit Katiyar

Javascript

<script>
 
// JavaScript program to implement
// the above approach
 
// Function to precompute the
// factorial of 1 to N
function calculateFact(fact, N)
{
    fact[0] = 1;
    for (var i = 1; i < N; i++) {
        fact[i] = fact[i - 1] * i;
    }
}
 
// Function to get the value of nCr
function nCr(fact, N, R)
{
    if (R > N)
        return 0;
 
    // nCr= fact(n)/(fact(r)*fact(n-r))
    var res = parseInt(fact[N] / fact[R]);
    res = parseInt(res / fact[N - R]);
 
    return res;
}
 
// Function to count the number of ways
// to rearrange the array to obtain same BST
function countWays(arr, fact)
{
    // Store the size of the array
    var N = arr.length;
 
    // Base case
    if (N <= 2) {
        return 1;
    }
 
    // Store the elements of the
    // left subtree of BST
    var leftSubTree = [];
 
    // Store the elements of the
    // right subtree of BST
    var rightSubTree = [];
 
    // Store the root node
    var root = arr[0];
 
    for (var i = 1; i < N; i++) {
 
        // Push all the elements
        // of the left subtree
        if (arr[i] < root) {
            leftSubTree.push(
                arr[i]);
        }
 
        // Push all the elements
        // of the right subtree
        else {
            rightSubTree.push(
                arr[i]);
        }
    }
 
    // Store the size of leftSubTree
    var N1 = leftSubTree.length;
 
    // Store the size of rightSubTree
    var N2 = rightSubTree.length;
 
    // Recurrence relation
    var countLeft
        = countWays(leftSubTree,
                    fact);
    var countRight
        = countWays(rightSubTree,
                    fact);
 
    return nCr(fact, N - 1, N1)
           * countLeft * countRight;
}
 
// Driver Code
 
var arr = [];
arr = [3, 4, 5, 1, 2];
 
// Store the size of arr
var N = arr.length;
 
// Store the factorial up to N
var fact = Array(N);
 
// Precompute the factorial up to N
calculateFact(fact, N);
document.write( countWays(arr, fact));
 
</script>
Producción: 

6

Tiempo Complejidad: O(N 2 )
Espacio Auxiliar: O(N)

Publicación traducida automáticamente

Artículo escrito por shobhitgupta907 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *