Número de formas de formar un montón con n enteros distintos

Posted on by Rudeus Greyrat

Dado n, ¿cuántos Max Heap distintos se pueden hacer a partir de n enteros distintos?

Ejemplos: 

Input : n = 3
Output : Assume the integers are 1, 2, 3.
Then the 2 possible max heaps are:       
            3
           / \
          1   2

           3
          / \
         2   1

Input : n = 4
Output : Assume the integers are 1, 2, 3, 4.
Then the 3 possible max heaps are:
        4 
       / \ 
      3   2 
     / 
    1

        4 
       / \ 
      2   3 
     / 
    1

        4 
       / \ 
      3   1 
     / 
    2

Como solo hay un elemento como raíz , debe ser el número más grande. Ahora tenemos n-1 elementos restantes. La observación principal aquí es que debido a las propiedades máximas del montón, la estructura de los Nodes del montón seguirá siendo la misma en todas las instancias, pero solo cambiarán los valores en los Nodes. 

Suponga que hay l elementos en el subárbol izquierdo y r elementos en el subárbol derecho . Ahora para la raíz, l + r = n-1. A partir de esto, podemos ver que podemos elegir cualquier l de los n-1 elementos restantes para el subárbol izquierdo, ya que todos son más pequeños que la raíz. 

Sabemos que hay  \binom{n-1}{l} maneras de hacer esto. A continuación, para cada instancia de estos, podemos tener muchos montones con l elementos y para cada uno de ellos podemos tener muchos montones con r elementos. Así podemos considerarlos como subproblemas y recurrir a la respuesta final como: 
T(n) =  \binom{n-1}{l} * T(L) * T(R).

Ahora tenemos que encontrar los valores de l y r para un n dado. Sabemos que la altura del montón h =  \ log_2 n . También el número máximo de elementos que pueden estar presentes en el nivel h de cualquier montón, m =  2^h , donde la raíz está en el nivel 0. Además, el número de elementos realmente presentes en el último nivel del montón p = n – ( 2^h – 1). (desde  2^h - 1 número de Nodes presentes hasta el penúltimo nivel). Así, puede haber dos casos : cuando el último nivel está más o igual a la mitad: 
l =  2^h – 1, si p >= m / 2 

(o) el último nivel está a menos de la mitad: 
l =  2^h – 1 – ((m / 2) – p), si p < m / 2 
(obtenemos  2^h – 1 aquí porque el subárbol izquierdo tiene  2^0 + 2^1 +..+2^{h-1} Nodes. 
A partir de esto podemos decir también que r = n – l – 1.

Podemos usar el enfoque de programación dinámica discutido en esta publicación aquí para encontrar los valores de  \binom{n}{k} . De manera similar, si observamos el árbol de recurrencia para la recurrencia óptima de la subestructura formada anteriormente, podemos ver que también tiene la propiedad de subproblemas superpuestos , por lo tanto, se puede resolver mediante programación dinámica: 

             T(7)
            /    \
          T(3)   T(3)
         /  \     /  \    
     T(1)  T(1) T(1) T(1)

La siguiente es la implementación del enfoque anterior: 

C++

// CPP program to count max heaps with n distinct keys
#include <iostream>
using namespace std;
 
#define MAXN 105 // maximum value of n here
 
// dp[i] = number of max heaps for i distinct integers
int dp[MAXN];
 
// nck[i][j] = number of ways to choose j elements
//             form i elements, no order */
int nck[MAXN][MAXN];
 
// log2[i] = floor of logarithm of base 2 of i
int log2[MAXN];
 
// to calculate nCk
int choose(int n, int k)
{
    if (k > n)
        return 0;
    if (n <= 1)
        return 1;
    if (k == 0)
        return 1;
 
    if (nck[n][k] != -1)
        return nck[n][k];
 
    int answer = choose(n - 1, k - 1) + choose(n - 1, k);
    nck[n][k] = answer;
    return answer;
}
 
// calculate l for give value of n
int getLeft(int n)
{
    if (n == 1)
        return 0;
 
    int h = log2[n];
 
    // max number of elements that can be present in the
    // hth level of any heap
    int numh = (1 << h); //(2 ^ h)
 
    // number of elements that are actually present in
    // last level(hth level)
    // (2^h - 1)
    int last = n - ((1 << h) - 1);
 
    // if more than half-filled
    if (last >= (numh / 2))
        return (1 << h) - 1; // (2^h) - 1
    else
        return (1 << h) - 1 - ((numh / 2) - last);
}
 
// find maximum number of heaps for n
int numberOfHeaps(int n)
{
    if (n <= 1)
        return 1;
 
    if (dp[n] != -1)
        return dp[n];
 
    int left = getLeft(n);
    int ans = (choose(n - 1, left) * numberOfHeaps(left)) *
                             (numberOfHeaps(n - 1 - left));
    dp[n] = ans;
    return ans;
}
 
// function to initialize arrays
int solve(int n)
{
    for (int i = 0; i <= n; i++)
        dp[i] = -1;
 
    for (int i = 0; i <= n; i++)
        for (int j = 0; j <= n; j++)
            nck[i][j] = -1;
 
    int currLog2 = -1;
    int currPower2 = 1;
 
    // for each power of two find logarithm
    for (int i = 1; i <= n; i++) {
        if (currPower2 == i) {
            currLog2++;
            currPower2 *= 2;
        }
        log2[i] = currLog2;
    }
 
    return numberOfHeaps(n);
}
 
// driver function
int main()
{
    int n = 10;
    cout << solve(n) << endl;
    return 0;
}

Java

// Java program to count max heaps with n distinct keys
class GFG
{
 
    static int MAXN = 105; // maximum value of n here
 
    // dp[i] = number of max heaps for i distinct integers
    static int[] dp = new int[MAXN];
 
    // nck[i][j] = number of ways to choose j elements
    //         form i elements, no order */
    static int[][] nck = new int[MAXN][MAXN];
 
    // log2[i] = floor of logarithm of base 2 of i
    static int[] log2 = new int[MAXN];
 
    // to calculate nCk
    public static int choose(int n, int k)
    {
        if (k > n)
        {
            return 0;
        }
        if (n <= 1)
        {
            return 1;
        }
        if (k == 0)
        {
            return 1;
        }
 
        if (nck[n][k] != -1)
        {
            return nck[n][k];
        }
 
        int answer = choose(n - 1, k - 1) + choose(n - 1, k);
        nck[n][k] = answer;
        return answer;
    }
 
    // calculate l for give value of n
    public static int getLeft(int n)
    {
        if (n == 1)
        {
            return 0;
        }
 
        int h = log2[n];
 
        // max number of elements that can be present in the
        // hth level of any heap
        int numh = (1 << h); //(2 ^ h)
 
        // number of elements that are actually present in
        // last level(hth level)
        // (2^h - 1)
        int last = n - ((1 << h) - 1);
 
        // if more than half-filled
        if (last >= (numh / 2))
        {
            return (1 << h) - 1; // (2^h) - 1
        }
        else
        {
            return (1 << h) - 1 - ((numh / 2) - last);
        }
    }
 
    // find maximum number of heaps for n
    public static int numberOfHeaps(int n)
    {
        if (n <= 1)
        {
            return 1;
        }
 
        if (dp[n] != -1)
        {
            return dp[n];
        }
 
        int left = getLeft(n);
        int ans = (choose(n - 1, left) * numberOfHeaps(left))
                * (numberOfHeaps(n - 1 - left));
        dp[n] = ans;
        return ans;
    }
 
    // function to initialize arrays
    public static int solve(int n)
    {
        for (int i = 0; i <= n; i++)
        {
            dp[i] = -1;
        }
 
        for (int i = 0; i <= n; i++)
        {
            for (int j = 0; j <= n; j++)
            {
                nck[i][j] = -1;
            }
        }
 
        int currLog2 = -1;
        int currPower2 = 1;
 
        // for each power of two find logarithm
        for (int i = 1; i <= n; i++)
        {
            if (currPower2 == i)
            {
                currLog2++;
                currPower2 *= 2;
            }
            log2[i] = currLog2;
        }
 
        return numberOfHeaps(n);
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int n = 10;
        System.out.print(solve(n));
    }
}
 
// This code has been contributed by 29AjayKumar

Python3

# Python program to count max heaps with n distinct keys
 
MAXN = 105 # maximum value of n here
 
# dp[i] = number of max heaps for i distinct integers
dp = [0]*MAXN
 
# nck[i][j] = number of ways to choose j elements
#             form i elements, no order */
nck = [[0 for i in range(MAXN)] for j in range(MAXN)]
 
# log2[i] = floor of logarithm of base 2 of i
log2 = [0]*MAXN
 
# to calculate nCk
def choose(n, k):
    if (k > n):
        return 0
    if (n <= 1):
        return 1
    if (k == 0):
        return 1
 
    if (nck[n][k] != -1):
        return nck[n][k]
 
    answer = choose(n - 1, k - 1) + choose(n - 1, k)
    nck[n][k] = answer
    return answer
 
 
# calculate l for give value of n
def getLeft(n):
    if (n == 1):
        return 0
 
    h = log2[n]
 
    # max number of elements that can be present in the
    # hth level of any heap
    numh = (1 << h) #(2 ^ h)
 
    # number of elements that are actually present in
    # last level(hth level)
    # (2^h - 1)
    last = n - ((1 << h) - 1)
 
    # if more than half-filled
    if (last >= (numh // 2)):
        return (1 << h) - 1 # (2^h) - 1
    else:
        return (1 << h) - 1 - ((numh // 2) - last)
 
 
# find maximum number of heaps for n
def numberOfHeaps(n):
    if (n <= 1):
        return 1
 
    if (dp[n] != -1):
        return dp[n]
 
    left = getLeft(n)
    ans = (choose(n - 1, left) * numberOfHeaps(left)) * (numberOfHeaps(n - 1 - left))
    dp[n] = ans
    return ans
 
 
# function to initialize arrays
def solve(n):
    for i in range(n+1):
        dp[i] = -1
 
    for i in range(n+1):
        for j in range(n+1):
            nck[i][j] = -1
 
    currLog2 = -1
    currPower2 = 1
 
    # for each power of two find logarithm
    for i in range(1,n+1):
        if (currPower2 == i):
            currLog2 += 1
            currPower2 *= 2
        log2[i] = currLog2
    return numberOfHeaps(n)
 
 
# Driver code
n = 10
print(solve(n))
 
# This code is contributed by ankush_953

C#

// C# program to count max heaps with n distinct keys
using System;
   
class GFG
{
    static int MAXN = 105; // maximum value of n here
       
    // dp[i] = number of max heaps for i distinct integers
    static int[] dp = new int[MAXN]; 
       
    // nck[i][j] = number of ways to choose j elements
    //             form i elements, no order */
    static int[,] nck = new int[MAXN,MAXN]; 
       
    // log2[i] = floor of logarithm of base 2 of i
    static int[] log2 = new int[MAXN]; 
       
    // to calculate nCk
    public static int choose(int n, int k)
    {
        if (k > n)
            return 0;
        if (n <= 1)
            return 1;
        if (k == 0)
            return 1;
       
        if (nck[n,k] != -1)
            return nck[n,k];
       
        int answer = choose(n - 1, k - 1) + choose(n - 1, k);
        nck[n,k] = answer;
        return answer;
    }
       
    // calculate l for give value of n
    public static int getLeft(int n)
    {
        if (n == 1)
            return 0;
       
        int h = log2[n];
       
        // max number of elements that can be present in the 
        // hth level of any heap
        int numh = (1 << h); //(2 ^ h)
       
        // number of elements that are actually present in
        // last level(hth level)
        // (2^h - 1)
        int last = n - ((1 << h) - 1);
       
        // if more than half-filled
        if (last >= (numh / 2))
            return (1 << h) - 1; // (2^h) - 1
        else
            return (1 << h) - 1 - ((numh / 2) - last);
    }
       
    // find maximum number of heaps for n
    public static int numberOfHeaps(int n)
    {
        if (n <= 1)
            return 1;
       
        if (dp[n] != -1)
            return dp[n];
       
        int left = getLeft(n);
        int ans = (choose(n - 1, left) * numberOfHeaps(left)) * 
                                 (numberOfHeaps(n - 1 - left));
        dp[n] = ans;
        return ans;
    }
       
    // function to initialize arrays
    public static int solve(int n)
    {
        for (int i = 0; i <= n; i++)
            dp[i] = -1;
       
        for (int i = 0; i <= n; i++)
            for (int j = 0; j <= n; j++)
                nck[i,j] = -1;
       
        int currLog2 = -1;
        int currPower2 = 1;
       
        // for each power of two find logarithm
        for (int i = 1; i <= n; i++) {
            if (currPower2 == i) {
                currLog2++;
                currPower2 *= 2;
            }
            log2[i] = currLog2;
        }
       
        return numberOfHeaps(n);
    }
       
    // driver function
    static void Main()
    {
        int n = 10;
        Console.Write(solve(n));
    }
    //This code is contributed by DrRoot_
}

Javascript

<script>
 
// JavaScript program to count max heaps with n distinct keys
 
let MAXN = 105; // maximum value of n here
 
// dp[i] = number of max heaps for i distinct integers
let dp = new Array(MAXN);
 
// nck[i][j] = number of ways to choose j elements
    //         form i elements, no order */
let nck = new Array(MAXN);
for(let i=0;i<MAXN;i++)
{
    nck[i]=new Array(MAXN);
    for(let j=0;j<MAXN;j++)
        nck[i][j]=0;
}
 
// log2[i] = floor of logarithm of base 2 of i
let log2 = new Array(MAXN);
 
 // to calculate nCk
function choose(n,k)
{
    if (k > n)
        {
            return 0;
        }
        if (n <= 1)
        {
            return 1;
        }
        if (k == 0)
        {
            return 1;
        }
   
        if (nck[n][k] != -1)
        {
            return nck[n][k];
        }
   
        let answer = choose(n - 1, k - 1) + choose(n - 1, k);
        nck[n][k] = answer;
        return answer;
}
 
 // calculate l for give value of n
function getLeft(n)
{
    if (n == 1)
        {
            return 0;
        }
   
        let h = log2[n];
   
        // max number of elements that can be present in the
        // hth level of any heap
        let numh = (1 << h); //(2 ^ h)
   
        // number of elements that are actually present in
        // last level(hth level)
        // (2^h - 1)
        let last = n - ((1 << h) - 1);
   
        // if more than half-filled
        if (last >= (numh / 2))
        {
            return (1 << h) - 1; // (2^h) - 1
        }
        else
        {
            return (1 << h) - 1 - ((numh / 2) - last);
        }
}
 
// find maximum number of heaps for n
function numberOfHeaps(n)
{
    if (n <= 1)
        {
            return 1;
        }
   
        if (dp[n] != -1)
        {
            return dp[n];
        }
   
        let left = getLeft(n);
        let ans = (choose(n - 1, left) * numberOfHeaps(left))
                * (numberOfHeaps(n - 1 - left));
        dp[n] = ans;
        return ans;
}
 
// function to initialize arrays
function solve(n)
{
    for (let i = 0; i <= n; i++)
        {
            dp[i] = -1;
        }
   
        for (let i = 0; i <= n; i++)
        {
            for (let j = 0; j <= n; j++)
            {
                nck[i][j] = -1;
            }
        }
   
        let currLog2 = -1;
        let currPower2 = 1;
   
        // for each power of two find logarithm
        for (let i = 1; i <= n; i++)
        {
            if (currPower2 == i)
            {
                currLog2++;
                currPower2 *= 2;
            }
            log2[i] = currLog2;
        }
   
        return numberOfHeaps(n);
}
 
// Driver code
let n = 10;
document.write(solve(n));
 
// This code is contributed by rag2127
 
</script>
Producción

3360

Publicación traducida automáticamente

Artículo escrito por rsatish1110 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 *