Cuente el número de formas de dividir un conjunto en k subconjuntos

Dados dos números n y k donde n representa una cantidad de elementos en un conjunto, encuentre varias formas de dividir el conjunto en k subconjuntos.
Ejemplo: 

Input: n = 3, k = 2
Output: 3
Explanation: Let the set be {1, 2, 3}, we can partition
             it into 2 subsets in following ways
             {{1,2}, {3}},  {{1}, {2,3}},  {{1,3}, {2}}  

Input: n = 3, k = 1
Output: 1
Explanation: There is only one way {{1, 2, 3}}

Solución recursiva

• Enfoque: en primer lugar, definamos una solución recursiva para encontrar la solución para el elemento n. Hay dos casos. 
  1. Los n – 1 elementos anteriores se dividen en k particiones, es decir, S(n-1,k) vías. Coloque este n-ésimo elemento en una de las k particiones anteriores. Entonces, cuenta = k * S(n-1, k)
  2. Los n – 1 elementos anteriores se dividen en k – 1 particiones, es decir, S(n-1, k-1) vías. Coloque el elemento n en una nueva partición (partición de un solo elemento). Entonces, cuenta = S (n-1, k-1)
  3. Recuento total = k * S(n-1, k) + S(n-1, k-1).
• Algoritmo: 
  1. Cree una función recursiva que acepte dos parámetros, n y k. La función devuelve el número total de particiones de n elementos en k conjuntos.
  2. Manejar los casos base. Si n = 0 o k = 0 o k > n devuelve 0 porque no puede haber ningún subconjunto. Si n es igual a k o k es igual a 1 devuelve 1.
  3. De lo contrario, calcule el valor de la siguiente manera: S (n, k) = k * S (n-1, k) + S (n-1, k-1) , es decir, llame a la función recursiva con el parámetro recurido y calcule el valor de S (n, k).
  4. Devolver la suma.
• Implementación:

// A C++ program to count number of partitions
// of a set with n elements into k subsets
#include<iostream>
using namespace std;
 
// Returns count of different partitions of n
// elements in k subsets
int countP(int n, int k)
{
  // Base cases
  if (n == 0 || k == 0 || k > n)
     return 0;
  if (k == 1 || k == n)
      return 1;
 
  // S(n+1, k) = k*S(n, k) + S(n, k-1)
  return  k*countP(n-1, k) + countP(n-1, k-1);
}
 
// Driver program
int main()
{
   cout <<  countP(3, 2);
   return 0;
}

// Java  program to count number
// of partitions of a set with
// n elements into k subsets
import java.io.*;
 
class GFG
{
    // Returns count of different
    // partitions of n elements in
    // k subsets
    public static int countP(int n, int k)
    {
       // Base cases
       if (n == 0 || k == 0 || k > n)
          return 0;
       if (k == 1 || k == n)
          return 1;
 
       // S(n+1, k) = k*S(n, k) + S(n, k-1)
       return (k * countP(n - 1, k)
              + countP(n - 1, k - 1));
    }
 
    // Driver program
    public static void main(String args[])
    {
       System.out.println(countP(3, 2));
 
    }
}
 
//This code is contributed by Anshika Goyal.

# A Python3 program to count number
# of partitions of a set with n
# elements into k subsets
 
# Returns count of different partitions
# of n elements in k subsets
def countP(n, k):
     
    # Base cases
    if (n == 0 or k == 0 or k > n):
        return 0
    if (k == 1 or k == n):
        return 1
     
    # S(n+1, k) = k*S(n, k) + S(n, k-1)
    return (k * countP(n - 1, k) +
                countP(n - 1, k - 1))
 
# Driver Code
if __name__ == "__main__":
    print(countP(3, 2))
 
# This code is contributed
# by Akanksha Rai(Abby_akku)

// C# program to count number
// of partitions of a set with
// n elements into k subsets
using System;
 
class GFG {
     
    // Returns count of different
    // partitions of n elements in
    // k subsets
    public static int countP(int n, int k)
    {
         
        // Base cases
        if (n == 0 || k == 0 || k > n)
            return 0;
        if (k == 1 || k == n)
            return 1;
     
        // S(n+1, k) = k*S(n, k) + S(n, k-1)
        return (k * countP(n - 1, k)
                + countP(n - 1, k - 1));
    }
 
    // Driver program
    public static void Main()
    {
        Console.WriteLine(countP(3, 2));
    }
}
 
// This code is contributed by anuj_67.

<?php
// A PHP program to count
// number of partitions of
// a set with n elements
// into k subsets
 
// Returns count of different
// partitions of n elements
// in k subsets
function countP($n, $k)
{
    // Base cases
    if ($n == 0 || $k == 0 || $k > $n)
        return 0;
    if ($k == 1 || $k == $n)
        return 1;
     
    // S(n+1, k) = k*S(n, k)
    // + S(n, k-1)
    return $k * countP($n - 1, $k) +
            countP($n - 1, $k - 1);
}
 
    // Driver Code
    echo countP(3, 2);
 
// This code is contributed by aj_36
?>

<script>
// Javascript  program to count number
// of partitions of a set with
// n elements into k subsets
     
    // Returns count of different
    // partitions of n elements in
    // k subsets
    function countP(n, k)
    {
     
        // Base cases
       if (n == 0 || k == 0 || k > n)
          return 0;
       if (k == 1 || k == n)
          return 1;
  
       // S(n + 1, k) = k*S(n, k) + S(n, k - 1)
       return (k * countP(n - 1, k)
              + countP(n - 1, k - 1));
    }
     
    // Driver program
    document.write(countP(3, 2));
     
    // This code is contributed by avanitrachhadiya2155   
</script>

• Producción:

3

• Análisis de Complejidad: 
  • Complejidad temporal: O(2^n). 
    Para cada valor de n, se llaman dos funciones recursivas. Más específicamente, la complejidad del tiempo es exponencial.
  • Complejidad del espacio: O(n)(Debido a la pila de llamadas). 
     

Solución eficiente  

• Enfoque: La complejidad temporal de la solución recursiva anterior es exponencial. La solución se puede optimizar reduciendo los subproblemas superpuestos. A continuación se muestra el árbol de recursión de countP(10,7) . El subproblema countP(8,6) o CP(8,6) se llama varias veces.

• Así que este problema tiene ambas propiedades (ver Tipo 1 y Tipo 2 ) de un problema de programación dinámica. Al igual que otros problemas típicos de programación dinámica (DP) , los cálculos de los mismos subproblemas se pueden evitar mediante la construcción de una array temporal dp[][] de forma ascendente utilizando la fórmula recursiva que se muestra.
  Luego viene la reducción de los subproblemas para optimizar la complejidad del problema. Esto se puede hacer de dos formas: 
  1. Modo ascendente: esto mantiene intacta la estructura recursiva y almacena los valores en un hashmap o una array 2D. Luego, calcule el valor solo una vez y, cuando se llame a la función, devuelva el valor.
  2. Manera de arriba hacia abajo: Esto mantiene una array 2D de tamaño n*k, donde dp[i][j] representa un número total de particiones de i elementos en j conjuntos. Complete los casos base para dp[i][0] y dp[0][i]. Para un valor (i,j), se necesitan los valores de dp[i-1][j] y dp[i-1][j-1]. Así que llene el DP desde la fila 0 hasta la n y la columna 0 hasta la k.
• Algoritmo: 
  1. Cree una array Dp dp[n+1][k+1] de tamaño ( n + 1 )* ( k + 1 ) .
  2. Rellene los valores de los casos básicos. Para todos los valores de i de 0 a n complete dp[i][0] = 0 y para todos los valores de i de 0 a k complete dp[0][k] = 0
  3. Ejecute un ciclo anidado, el ciclo externo de 1 a n y el ciclo interno de 1 a k.
  4. Para el índice i y j (bucle exterior y bucle interior respectivamente), calcule dp[i][j] = j * dp[i – 1][j] + dp[i – 1][j – 1] y si j = = 1 o i == j, calcule dp[i][j] = 1.
  5. Imprimir valores dp[n][k]
• Implementación:

// A Dynamic Programming based C++ program to count
// number of partitions of a set with n elements
// into k subsets
#include<iostream>
using namespace std;
 
// Returns count of different partitions of n
// elements in k subsets
int countP(int n, int k)
{
  // Table to store results of subproblems
  int dp[n+1][k+1];
 
  // Base cases
  for (int i = 0; i <= n; i++)
     dp[i][0] = 0;
  for (int i = 0; i <= k; i++)
     dp[0][k] = 0;
 
  // Fill rest of the entries in dp[][]
  // in bottom up manner
  for (int i = 1; i <= n; i++)
     for (int j = 1; j <= i; j++)
       if (j == 1 || i == j)
          dp[i][j] = 1;
       else
          dp[i][j] = j * dp[i - 1][j] + dp[i - 1][j - 1];
 
  return dp[n][k];
}
 
// Driver program
int main()
{
   cout <<  countP(5, 2);
   return 0;
}

// A Dynamic Programming based Java program to count
// number of partitions of a set with n elements
// into k subsets
class GFG{
 
// Returns count of different partitions of n
// elements in k subsets
static int countP(int n, int k)
{
    // Table to store results of subproblems
    int[][] dp = new int[n+1][k+1];
     
    // Base cases
    for (int i = 0; i <= n; i++)
    dp[i][0] = 0;
    for (int i = 0; i <= k; i++)
    dp[0][k] = 0;
     
    // Fill rest of the entries in dp[][]
    // in bottom up manner
    for (int i = 1; i <= n; i++)
    for (int j = 1; j <= k; j++)
    if (j == 1 || i == j)
        dp[i][j] = 1;
    else
        dp[i][j] = j * dp[i - 1][j] + dp[i - 1][j - 1];
         
        return dp[n][k];
     
}
 
// Driver program
public static void main(String[] args )
{
    System.out.println(countP(5, 2));
}
}
 
// This code is contributed by Rajput-Ji

# A Dynamic Programming based Python3 program
# to count number of partitions of a set with
# n elements into k subsets
 
# Returns count of different partitions
# of n elements in k subsets
def countP(n, k):
     
    # Table to store results of subproblems
    dp = [[0 for i in range(k + 1)]
             for j in range(n + 1)]
 
    # Base cases
    for i in range(n + 1):
        dp[i][0] = 0
 
    for i in range(k + 1):
        dp[0][k] = 0
 
    # Fill rest of the entries in
    # dp[][] in bottom up manner
    for i in range(1, n + 1):
        for j in range(1, k + 1):
            if (j == 1 or i == j):
                dp[i][j] = 1
            else:
                dp[i][j] = (j * dp[i - 1][j] +
                                dp[i - 1][j - 1])
                 
    return dp[n][k]
 
# Driver Code
if __name__ == '__main__':
    print(countP(5, 2))
 
# This code is contributed by
# Surendra_Gangwar

// A Dynamic Programming based C# program 
// to count number of partitions of a 
// set with n elements into k subsets
using System;
 
class GFG
{
 
// Returns count of different partitions of n
// elements in k subsets
static int countP(int n, int k)
{
    // Table to store results of subproblems
    int[,] dp = new int[n + 1, k + 1];
     
    // Base cases
    for (int i = 0; i <= n; i++)
        dp[i, 0] = 0;
    for (int i = 0; i <= k; i++)
        dp[0, k] = 0;
     
    // Fill rest of the entries in dp[][]
    // in bottom up manner
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= k; j++)
            if (j == 1 || i == j)
                dp[i, j] = 1;
            else
                dp[i, j] = j * dp[i - 1, j] + dp[i - 1, j - 1];
             
        return dp[n, k];
     
}
 
// Driver code
public static void Main( )
{
    Console.Write(countP(5, 2));
}
}
 
// This code is contributed by Ita_c.

<?php
// A Dynamic Programming based PHP
// program to count number of
// partitions of a set with n 
// elements into k subsets
 
// Returns count of different
// partitions of n elements in
// k subsets
function countP($n, $k)
{
     
// Table to store results
// of subproblems
$dp[$n + 1][$k + 1] = array(array());
 
// Base cases
for ($i = 0; $i <= $n; $i++)
    $dp[$i][0] = 0;
for ($i = 0; $i <= $k; $i++)
    $dp[0][$k] = 0;
 
// Fill rest of the entries in
// dp[][] in bottom up manner
for ($i = 1; $i <= $n; $i++)
    for ($j = 1; $j <= $i; $j++)
    if ($j == 1 || $i == $j)
        $dp[$i][$j] = 1;
    else
        $dp[$i][$j] = $j * $dp[$i - 1][$j] +
                           $dp[$i - 1][$j - 1];
 
return $dp[$n][$k];
}
 
// Driver Code
echo countP(5, 2);
 
// This code is contributed by jit_t
?>

<script>
// A Dynamic Programming based Javascript program to count
// number of partitions of a set with n elements
// into k subsets
     
    // Returns count of different partitions of n
    // elements in k subsets
    function countP(n,k)
    {
        // Table to store results of subproblems
        let dp = new Array(n+1);
        for(let i = 0; i < n + 1; i++)
        {
            dp[i] = new Array(k+1);
            for(let j = 0; j < k + 1; j++)
            {
                dp[i][j] = -1;
            }
        }
         
          
        // Base cases
        for (let i = 0; i <= n; i++)
            dp[i][0] = 0;
        for (let i = 0; i <= k; i++)
            dp[0][k] = 0;
          
        // Fill rest of the entries in dp[][]
        // in bottom up manner
        for (let i = 1; i <= n; i++)
            for (let j = 1; j <= k; j++)
            if (j == 1 || i == j)
                dp[i][j] = 1;
            else
                dp[i][j] = j * dp[i - 1][j] + dp[i - 1][j - 1];
              
        return dp[n][k];
    }
     
    // Driver program
    document.write(countP(5, 2))
     
    // This code is contributed by rag2127
</script>

• Producción:

15

• Análisis de Complejidad: 
  • Complejidad temporal: O(n*k). 
    La array 2D dp de tamaño n*k está llena, por lo que la Complejidad de tiempo es O(n*k).
  • Complejidad espacial: O(n*k). 
    Se requiere una array DP 2D adicional.

Artículo similar: Bell Numbers 
Este artículo es una contribución de Rajeev Agrawal . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.