Skip to content

Instantly share code, notes, and snippets.

@tkmharris
Last active February 17, 2022 22:31
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save tkmharris/fe620ee24f4c102c7edcbd878dda3393 to your computer and use it in GitHub Desktop.
Save tkmharris/fe620ee24f4c102c7edcbd878dda3393 to your computer and use it in GitHub Desktop.
Generate Bell numbers using the Bell triangle
{-- 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` --}
"""
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