Last active
February 17, 2022 22:31
-
-
Save tkmharris/fe620ee24f4c102c7edcbd878dda3393 to your computer and use it in GitHub Desktop.
Generate Bell numbers using the Bell triangle
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
{-- Haskell function for getting the Bell numbers via the Bell triangle --} | |
{-- Bell number B_n is the number of partitions of {1,...,n} into nonempty subsets. | |
The Bell triangle A_{i,j}, 0<=j<=i is defined as follows: | |
1. A_{0,0} = 1 | |
2. A_{i+1,0} = A_{i,i} | |
3. A_{i+1,j+1} = A_{i+1,j} + A_{i,j} | |
The Bell numbers can then be read off as B_n = A_{n,0} | |
Everything evaluates lazily, so we can do this nicely with infinite lists.--} | |
bellNums :: [Int] | |
bellNums = map head $ iterate nextRow [1] where | |
nextRow xs = (last xs) : zipWith (+) xs (nextRow xs) -- iteratively define the rows of the Bell Triangle | |
{-- we can then get the first n Bell numbers with | |
`take n bellNums` --} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
""" | |
Methods for working with Bell numbers. | |
The n-th Bell number B_n is the number of ways to partition an n-element set into nonempty components. | |
""" | |
def bell_triangle(numRows): | |
""" | |
Get the first numRows rows of the Bell Triangle. | |
(Return empty list if numRows <= 0) | |
numRows: int | |
rtype: [[int]] | |
""" | |
if numRows <= 0: | |
return [] | |
bell_triangle = [[1]] | |
for i in range(numRows-1): | |
bell_triangle.append([bell_triangle[i][-1]]) | |
for j in range(i+1): | |
bell_triangle[i+1].append(bell_triangle[i][j] + bell_triangle[i+1][-1]) | |
return bell_triangle | |
def bell_number(num): | |
""" | |
Get num-th Bell number (return 0 if num <= 0). | |
num: int | |
rtype: int | |
""" | |
if num <= 0: | |
return 0 | |
currRow = [1] | |
for i in range(num-1): | |
nextRow = [currRow[-1]] | |
for j in range(i+1): | |
nextRow.append(currRow[j] + nextRow[-1]) | |
currRow = nextRow | |
return currRow[-1] | |
def bell_numbers(num): | |
""" | |
Get first num Bell numbers (return [] if num <= 0). | |
num: int | |
rtype: [int] | |
""" | |
if num <= 0: | |
return [] | |
bell_nums = [1] | |
currRow = [1] | |
for i in range(num-1): | |
nextRow = [currRow[-1]] | |
for j in range(i+1): | |
nextRow.append(currRow[j] + nextRow[-1]) | |
currRow = nextRow | |
bell_nums.append(currRow[-1]) | |
return bell_nums |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment