Dado un conjunto de n elementos, encuentre varias formas de dividirlo.
Ejemplos:
Input: n = 2
Output: Number of ways = 2
Explanation: Let the set be {1, 2}
{ {1}, {2} }
{ {1, 2} }
Input: n = 3
Output: Number of ways = 5
Explanation: Let the set be {1, 2, 3}
{ {1}, {2}, {3} }
{ {1}, {2, 3} }
{ {2}, {1, 3} }
{ {3}, {1, 2} }
{ {1, 2, 3} }.
La solución a las preguntas anteriores es Bell Number .
¿Qué es un número de campana?
Sea S(n, k) el número total de particiones de n elementos en k conjuntos. El valor del número de campana número n es la suma de S(n, k) para k = 1 a n. 
El valor de S(n, k) se puede definir recursivamente como, S(n+1, k) = k*S(n, k) + S(n, k-1)
¿Cómo funciona la fórmula recursiva anterior?
Cuando agregamos un elemento (n+1) a k particiones, hay dos posibilidades.
1) Se agrega como un solo conjunto de elementos a las particiones existentes, es decir, S(n, k-1)
2) Se agrega a todos los conjuntos de cada partición, es decir, k*S(n, k)
S(n, k) se llama números de Stirling de segunda clase
Los primeros números de Bell son 1, 1, 2, 5, 15, 52, 203, ….
AEl método simple para calcular el número de campana número n es calcular uno por uno S (n, k) para k = 1 an y devolver la suma de todos los valores calculados. Consulte esto para el cálculo de S(n, k).
A continuación se muestra la implementación basada en la programación dinámica del código recursivo anterior utilizando el número de Stirling:
C++
#include <iostream>
using namespace std;
int main() {
int n=5;
int s[n+1][n+1];
for(int i=0;i<n+1;i++){
for(int j=0;j<n+1;j++){
if(j>i) s[i][j]=0;
else if(i==j) s[i][j]=1;
else if(i==0 || j==0) s[i][j]=0;
else{
s[i][j]= j*s[i-1][j] + s[i-1][j-1];
}
}
}
int ans=0;
for(int i=0;i<n+1;i++){
ans += s[n][i];
}
cout<<ans;
return 0;
}
Java
/*package whatever //do not write package name here */
// Java program to find number of ways of partitioning it.
import java.io.*;
// "static void main" must be defined in a public class.
public class GFG {
public static void main(String[] args)
{
int n = 5;
int[][] s = new int[n + 1][n + 1];
for (int i = 0; i < n + 1; i++) {
for (int j = 0; j < n + 1; j++) {
if (j > i)
s[i][j] = 0;
else if (i == j)
s[i][j] = 1;
else if (i == 0 || j == 0)
s[i][j] = 0;
else {
s[i][j]
= j * s[i - 1][j] + s[i - 1][j - 1];
}
}
}
int ans = 0;
for (int i = 0; i < n + 1; i++) {
ans += s[n][i];
}
System.out.println(ans);
}
}
// The code is contributed by Gautam goel (gautamgoel962)
Python3
# python program to find number of ways of partitioning it. n = int(input()) s = [[0 for _ in range(n+1)] for _ in range(n+1)] for i in range(n+1): for j in range(n+1): if j > i: continue elif(i==j): s[i][j] = 1 elif(i==0 or j==0): s[i][j]=0 else: s[i][j] = j*s[i-1][j] + s[i-1][j-1] ans = 0 for i in range(0,n+1): ans+=s[n][i] print(ans)
C#
// C# Program to find number of ways of partitioning it.
using System;
public class Program {
static public void Main(string[] args) {
int n = 5;
int[, ] s = new int[n + 1, n + 1];
for (int i = 0; i < n + 1; i++) {
for (int j = 0; j < n + 1; j++) {
if (j > i)
s[i, j] = 0;
else if (i == j)
s[i, j] = 1;
else if (i == 0 || j == 0)
s[i, j] = 0;
else
s[i, j]
= j * s[i - 1, j] + s[i - 1, j - 1];
}
}
int ans = 0;
for (int i = 0; i < n + 1; i++)
ans += s[n, i];
Console.WriteLine(ans);
}
}
// This code is contributed by Tapesh(tapeshdua420)
Javascript
// JavaScript program to find number of ways of partitioning it.
let n=5;
let s = new Array(n+1);
for(let i=0;i<n+1;i++){
s[i] = new Array(n+1);
for(let j=0;j<n+1;j++){
if(j>i) s[i][j]=0;
else if(i==j) s[i][j]=1;
else if(i==0 || j==0) s[i][j]=0;
else{
s[i][j]= j*s[i-1][j] + s[i-1][j-1];
}
}
}
let ans=0;
for(let i=0;i<n+1;i++){
ans += s[n][i];
}
console.log(ans)
// The code is contributed by Gautam goel (gautamgoel962)
52
Complejidad temporal: O(N 2 )
Espacio Auxiliar: O(N 2 )
Un mejor método es usar Bell Triangle . A continuación se muestra un Triángulo de Campana de muestra para los primeros Números de Campana.
1 1 2 2 3 5 5 7 10 15 15 20 27 37 52
El triángulo se construye usando la siguiente fórmula.
// If this is first column of current row 'i' If j == 0 // Then copy last entry of previous row // Note that i'th row has i entries Bell(i, j) = Bell(i-1, i-1) // If this is not first column of current row Else // Then this element is sum of previous element // in current row and the element just above the // previous element Bell(i, j) = Bell(i-1, j-1) + Bell(i, j-1)
Interpretación
Entonces Bell(n, k) cuenta el número de particiones del conjunto {1, 2, …, n + 1} en las que el elemento k + 1 es el elemento más grande que puede estar solo en su conjunto.
Por ejemplo, Bell(3, 2) es 3, cuenta el número de particiones de {1, 2, 3, 4} en las que 3 es el elemento único más grande. Hay tres particiones de este tipo:
{1}, {2, 4}, {3}
{1, 4}, {2}, {3}
{1, 2, 4}, {3}.
A continuación se muestra la implementación basada en la programación dinámica de la fórmula recursiva anterior.
C++
// A C++ program to find n'th Bell number
#include<iostream>
using namespace std;
int bellNumber(int n)
{
int bell[n+1][n+1];
bell[0][0] = 1;
for (int i=1; i<=n; i++)
{
// Explicitly fill for j = 0
bell[i][0] = bell[i-1][i-1];
// Fill for remaining values of j
for (int j=1; j<=i; j++)
bell[i][j] = bell[i-1][j-1] + bell[i][j-1];
}
return bell[n][0];
}
// Driver program
int main()
{
for (int n=0; n<=5; n++)
cout << "Bell Number " << n << " is "
<< bellNumber(n) << endl;
return 0;
}
Java
// Java program to find n'th Bell number
import java.io.*;
class GFG
{
// Function to find n'th Bell Number
static int bellNumber(int n)
{
int[][] bell = new int[n+1][n+1];
bell[0][0] = 1;
for (int i=1; i<=n; i++)
{
// Explicitly fill for j = 0
bell[i][0] = bell[i-1][i-1];
// Fill for remaining values of j
for (int j=1; j<=i; j++)
bell[i][j] = bell[i-1][j-1] + bell[i][j-1];
}
return bell[n][0];
}
// Driver program
public static void main (String[] args)
{
for (int n=0; n<=5; n++)
System.out.println("Bell Number "+ n +
" is "+bellNumber(n));
}
}
// This code is contributed by Pramod Kumar
Python3
# A Python program to find n'th Bell number
def bellNumber(n):
bell = [[0 for i in range(n+1)] for j in range(n+1)]
bell[0][0] = 1
for i in range(1, n+1):
# Explicitly fill for j = 0
bell[i][0] = bell[i-1][i-1]
# Fill for remaining values of j
for j in range(1, i+1):
bell[i][j] = bell[i-1][j-1] + bell[i][j-1]
return bell[n][0]
# Driver program
for n in range(6):
print('Bell Number', n, 'is', bellNumber(n))
# This code is contributed by Soumen Ghosh
C#
// C# program to find n'th Bell number
using System;
class GFG {
// Function to find n'th
// Bell Number
static int bellNumber(int n)
{
int[,] bell = new int[n + 1,
n + 1];
bell[0, 0] = 1;
for (int i = 1; i <= n; i++)
{
// Explicitly fill for j = 0
bell[i, 0] = bell[i - 1, i - 1];
// Fill for remaining values of j
for (int j = 1; j <= i; j++)
bell[i, j] = bell[i - 1, j - 1] +
bell[i, j - 1];
}
return bell[n, 0];
}
// Driver Code
public static void Main ()
{
for (int n = 0; n <= 5; n++)
Console.WriteLine("Bell Number "+ n +
" is "+bellNumber(n));
}
}
// This code is contributed by nitin mittal.
PHP
<?php
// A PHP program to find
// n'th Bell number
// function that returns
// n'th bell number
function bellNumber($n)
{
$bell[0][0] = 1;
for ($i = 1; $i <= $n; $i++)
{
// Explicitly fill for j = 0
$bell[$i][0] = $bell[$i - 1]
[$i - 1];
// Fill for remaining
// values of j
for ($j = 1; $j <= $i; $j++)
$bell[$i][$j] = $bell[$i - 1][$j - 1] +
$bell[$i][$j - 1];
}
return $bell[$n][0];
}
// Driver Code
for ($n = 0; $n <= 5; $n++)
echo("Bell Number " . $n . " is "
. bellNumber($n) . "\n");
// This code is contributed by Ajit.
?>
Javascript
<script>
// Javascript program to find n'th Bell number
// Function to find n'th Bell Number
function bellNumber(n)
{
let bell = new Array(n+1);
for(let i = 0; i < n + 1; i++)
{
bell[i] = new Array(n + 1);
}
bell[0][0] = 1;
for (let i=1; i<=n; i++)
{
// Explicitly fill for j = 0
bell[i][0] = bell[i-1][i-1];
// Fill for remaining values of j
for (let j=1; j<=i; j++)
bell[i][j] = bell[i-1][j-1] + bell[i][j-1];
}
return bell[n][0];
}
for (let n=0; n<=5; n++)
document.write("Bell Number "+ n + " is "+bellNumber(n) + "</br>");
</script>
Producción:
Bell Number 0 is 1 Bell Number 1 is 1 Bell Number 2 is 2 Bell Number 3 is 5 Bell Number 4 is 15 Bell Number 5 is 52
Complejidad del tiempo: O(N 2 )
Espacio Auxiliar: O(N 2 )
Pronto discutiremos otros métodos más eficientes para calcular los números de Bell.
Otro problema que puede ser resuelto por Bell Numbers .
Un número no tiene cuadrados si no es divisible por un cuadrado perfecto que no sea 1. Por ejemplo, 6 es un número sin cuadrados pero 12 no lo es porque es divisible por 4.
Dado un número sin cuadrados x, encuentre el número de particiones multiplicativas diferentes de x El número de particiones multiplicativas es Bell(n) donde n es el número de factores primos de x. Por ejemplo x = 30, hay 3 factores primos de 2, 3 y 5. Entonces la respuesta es Bell(3) que es 5. Las 5 particiones son 1 x 30, 2 x15, 3 x 10, 5 x 6 y 2 x 3 x 5.
Ejercicio:
La implementación anterior provoca un desbordamiento aritmético para valores ligeramente mayores de n. Extienda el programa anterior para que los resultados se calculen bajo el módulo 1000000007 para evitar desbordamientos.
Referencia:
https://en.wikipedia.org/wiki/Bell_number
https://en.wikipedia.org/wiki/Bell_triangle
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.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA