bell数（对集合进行分区的方式数量） _数据结构

本文概述

C ++
Java
Python3
C#
PHP

给定一组n个元素, 请找到多种分区方法。
例子：

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

解决上述问题的方法是响铃号码.
什么是响铃号码？
【bell数（对集合进行分区的方式数量）】让
S(n, k)
是将n个元素划分为k个集合的总数。对于k = 1到n, 第n个贝尔号的值是S(n, k)的和。

文章图片
S(n, k)的值可以递归定义为S(n + 1, k)= k * S(n, k)+ S(n, k-1)
上述递归公式如何工作？
当我们将第(n + 1)个元素添加到k个分区时, 有两种可能性。
1)将其作为单个元素集添加到现有分区, 即S(n, k-1)
2)将其添加到每个分区的所有集合中, 即k * S(n, k)
S(n, k)被称为第二类斯特林数
前几个贝尔编号是1、1、2、5、15、52、203, ...。
一种简单方法要计算第n个贝尔数, 则将k = 1到n的计算S(n, k)一对一并返回所有计算值的总和。参考这个用于计算S(n, k)。
一种更好的方法用于钟形三角形。以下是前几个贝尔编号的示例贝尔三角形。

1 1 2 2 3 5 5 7 10 15 15 20 27 37 52

使用以下公式构造三角形。

// 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)

解释
然后Bell(n, k)计算集合{1, 2??, …, n + 1}的分区数, 其中元素k +1是该集合中可以单独存在的最大元素。
例如, Bell(3, 2)是3, 它是{1, 2, 3, 4}的分区数的计数, 其中3是最大的单例元素。有三个这样的分区：

{1}, {2, 4}, {3} {1, 4}, {2}, {3} {1, 2, 4}, {3}.

下面是上述递归公式的基于动态编程的实现。
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 numberdef 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# 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. ?>

输出如下：

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

上述解决方案的时间复杂度为O(n2)。我们很快将讨论计算贝尔数的其他更有效的方法。
贝尔数字可以解决的另一个问题
.
一个数字是
无平方
如果不能用除1以外的完美平方整除, 例如6是无平方数, 但不能用12除以4。
给定无平方数x, 找到x的不同乘法分区的数量。乘法分区的数量是Bell(n), 其中n是x的素数的数量。例如x = 30, 有3个素数分别为2、3和5。因此答案是Bell(3), 即5。5个分区是1 x 30、2 x15、3 x 10、5 x 6和2 3 x 5
行使：
上面的实现导致n的较大值发生算术溢出。扩展上面的程序, 以便以模1000000007计算结果, 以避免溢出。
参考：
https://en.wikipedia.org/wiki/Bell_number
https://en.wikipedia.org/wiki/Bell_triangle
本文作者：拉杰夫·阿格劳瓦尔(Rajeev Agrawal)。如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。