Bell Triangle
Bell Triangle is a pattern of numbers arranged in a triangular shape. It is named after Eric Temple Bell, a mathematician who made significant contributions to number theory. The Bell Triangle represents the Bell numbers, which are a sequence of numbers that count the number of ways a set with a certain number of elements can be partitioned into non-empty subsets. The Bell numbers start with 1 and increase rapidly as the number of elements in the set grows.
Problem Statement
The goal of the Bell Triangle problem is to generate the Bell Triangle for a given number of rows, where each row contains a sequence of Bell numbers.
Example
Let's consider generating the Bell Triangle with 4 rows.
The Bell Triangle for 4 rows will look like this:
1 1 2 2 3 5 5 7 10 15
Explanation
- In the first row, we have the first Bell number, which is 1.
- In the second row, we have the second Bell number, which is 2, and the third Bell number, which is 3.
- In the third row, we have the fourth Bell number, which is 5, the fifth Bell number, which is 7, and the sixth Bell number, which is 10.
- In the fourth row, we have the seventh Bell number, which is 15.
Each element in the Bell Triangle is obtained by adding the element in the previous row immediately to its left with the element in the current row immediately to its right.
Pseudocode and Algorithm
function generateBellTriangle(row):
if row <= 0:
return
// Create a 2D array to store the Bell Triangle
let result[2][row + 1]
// Initialize variables to keep track of the current row and the first element
let activeRow = 0
let back = 1
for i from 1 to row do:
// Set the first element of the current row to 'back'
result[activeRow][0] = back
// Set initial values for the other elements in the current row
for j from 1 to i do:
result[activeRow][j] = 0
// Calculate the elements in the current row and print them
for j from 1 to i do:
if activeRow is 0:
result[activeRow][j] = result[activeRow][j - 1] + result[1][j - 1]
else:
result[activeRow][j] = result[activeRow][j - 1] + result[0][j - 1]
print result[activeRow][j]
back = result[activeRow][j]
// Switch the active row for the next iteration
activeRow = 1 - activeRow
print newline
end function
The given code already provides an implementation of the Bell Triangle in C. Here's the standard pseudocode and algorithm for the same:
- Start with an empty 2D array
resultto store the Bell Triangle elements. - Initialize
activeRowto 0 to indicate the current row we are filling, andbackto 1 as the initial value for the first element. - For each row
ifrom 1 to the desired number of rows: a. Set the first element of the current row (result[activeRow][0]) to the value ofback. b. Set all other elements of the current row to the sum of the element immediately to their left in the same row (result[activeRow][j - 1]) and the element immediately to their left in the previous row (result[1 - activeRow][j - 1]). c. Print each element's value as it is calculated. d. Updatebackto the last element of the current row (result[activeRow][j]). e. Switch the value ofactiveRowbetween 0 and 1 to alternate between rows.
Code Solution
/*
C program for
Bell Triangle
*/
#include <stdio.h>
void bellTriangle(int row)
{
if (row <= 0)
{
return;
}
// Optimize result by only 2 rows
int result[2][row + 1];
// Current row
int activeRow = 0;
// First element
int back = 1;
for (int i = 1; i <= row; ++i)
{
// Previous row last element as
// first element in current row .
result[activeRow][0] = back;
// Set initial value
result[0][i] = 0;
result[1][i] = 0;
for (int j = 0; j < i; ++j)
{
if (j > 0)
{
if (activeRow == 0)
{
result[activeRow][j] =
result[activeRow][j - 1] +
result[1][j - 1];
}
else
{
result[activeRow][j] =
result[activeRow][j - 1] +
result[0][j - 1];
}
}
// Print element value
printf(" %d", result[activeRow][j]);
back = result[activeRow][j];
}
// Change active row
if (activeRow == 0)
{
activeRow = 1;
}
else
{
activeRow = 0;
}
printf("\n");
}
}
int main(int argc, char const *argv[])
{
/*
row = 8
----------
1
1 2
2 3 5
5 7 10 15
15 20 27 37 52
52 67 87 114 151 203
203 255 322 409 523 674 877
877 1080 1335 1657 2066 2589 3263 4140
*/
bellTriangle(8);
return 0;
}Output
1
1 2
2 3 5
5 7 10 15
15 20 27 37 52
52 67 87 114 151 203
203 255 322 409 523 674 877
877 1080 1335 1657 2066 2589 3263 4140/*
Java program for
Bell Triangle
*/
public class BellNumbers
{
public void bellTriangle(int row)
{
if (row <= 0)
{
return;
}
// Optimize result by only 2 rows
int[][] result = new int[row + 1][row + 1];
// Current row
int activeRow = 0;
// First element
int back = 1;
for (int i = 1; i <= row; ++i)
{
// Previous row last element as
// first element in current row .
result[activeRow][0] = back;
// Set initial value
result[0][i] = 0;
result[1][i] = 0;
for (int j = 0; j < i; ++j)
{
if (j > 0)
{
if (activeRow == 0)
{
result[activeRow][j] =
result[activeRow][j - 1] +
result[1][j - 1];
}
else
{
result[activeRow][j] =
result[activeRow][j - 1] +
result[0][j - 1];
}
}
// Print element value
System.out.print(" " + result[activeRow][j] );
back = result[activeRow][j];
}
// Change active row
if (activeRow == 0)
{
activeRow = 1;
}
else
{
activeRow = 0;
}
System.out.print("\n");
}
}
public static void main(String[] args)
{
BellNumbers task = new BellNumbers();
/*
row = 8
----------
1
1 2
2 3 5
5 7 10 15
15 20 27 37 52
52 67 87 114 151 203
203 255 322 409 523 674 877
877 1080 1335 1657 2066 2589 3263 4140
*/
task.bellTriangle(8);
}
}Output
1
1 2
2 3 5
5 7 10 15
15 20 27 37 52
52 67 87 114 151 203
203 255 322 409 523 674 877
877 1080 1335 1657 2066 2589 3263 4140// Include header file
#include <iostream>
using namespace std;
/*
C++ program for
Bell Triangle
*/
class BellNumbers
{
public: void bellTriangle(int row)
{
if (row <= 0)
{
return;
}
// Optimize result by only 2 rows
int result[row + 1][row + 1];
// Current row
int activeRow = 0;
// First element
int back = 1;
for (int i = 1; i <= row; ++i)
{
// Previous row last element as
// first element in current row .
result[activeRow][0] = back;
// Set initial value
result[0][i] = 0;
result[1][i] = 0;
for (int j = 0; j < i; ++j)
{
if (j > 0)
{
if (activeRow == 0)
{
result[activeRow][j] =
result[activeRow][j - 1] +
result[1][j - 1];
}
else
{
result[activeRow][j] =
result[activeRow][j - 1] +
result[0][j - 1];
}
}
// Print element value
cout << " " << result[activeRow][j];
back = result[activeRow][j];
}
// Change active row
if (activeRow == 0)
{
activeRow = 1;
}
else
{
activeRow = 0;
}
cout << "\n";
}
}
};
int main()
{
BellNumbers *task = new BellNumbers();
/*
row = 8
----------
1
1 2
2 3 5
5 7 10 15
15 20 27 37 52
52 67 87 114 151 203
203 255 322 409 523 674 877
877 1080 1335 1657 2066 2589 3263 4140
*/
task->bellTriangle(8);
return 0;
}Output
1
1 2
2 3 5
5 7 10 15
15 20 27 37 52
52 67 87 114 151 203
203 255 322 409 523 674 877
877 1080 1335 1657 2066 2589 3263 4140// Include namespace system
using System;
/*
Csharp program for
Bell Triangle
*/
public class BellNumbers
{
public void bellTriangle(int row)
{
if (row <= 0)
{
return;
}
// Optimize result by only 2 rows
int[,] result = new int[row + 1,row + 1];
// Current row
int activeRow = 0;
// First element
int back = 1;
for (int i = 1; i <= row; ++i)
{
// Previous row last element as
// first element in current row .
result[activeRow,0] = back;
// Set initial value
result[0,i] = 0;
result[1,i] = 0;
for (int j = 0; j < i; ++j)
{
if (j > 0)
{
if (activeRow == 0)
{
result[activeRow,j] =
result[activeRow,j - 1] + result[1,j - 1];
}
else
{
result[activeRow,j] =
result[activeRow,j - 1] + result[0,j - 1];
}
}
// Print element value
Console.Write(" " + result[activeRow,j]);
back = result[activeRow,j];
}
// Change active row
if (activeRow == 0)
{
activeRow = 1;
}
else
{
activeRow = 0;
}
Console.Write("\n");
}
}
public static void Main(String[] args)
{
BellNumbers task = new BellNumbers();
/*
row = 8
----------
1
1 2
2 3 5
5 7 10 15
15 20 27 37 52
52 67 87 114 151 203
203 255 322 409 523 674 877
877 1080 1335 1657 2066 2589 3263 4140
*/
task.bellTriangle(8);
}
}Output
1
1 2
2 3 5
5 7 10 15
15 20 27 37 52
52 67 87 114 151 203
203 255 322 409 523 674 877
877 1080 1335 1657 2066 2589 3263 4140package main
import "fmt"
/*
Go program for
Bell Triangle
*/
func bellTriangle(row int) {
if row <= 0 {
return
}
// Optimize result by only 2 rows
var result = make([][] int, 2)
for i:= 0; i < 2; i++{
result[i] = make([]int,row+1)
}
// Current row
var activeRow int = 0
// First element
var back int = 1
for i := 1 ; i <= row ; i++ {
// Previous row last element as
// first element in current row .
result[activeRow][0] = back
// Set initial value
result[0][i] = 0
result[1][i] = 0
for j := 0 ; j < i ; j++ {
if j > 0 {
if activeRow == 0 {
result[activeRow][j] = result[activeRow][j - 1] +
result[1][j - 1]
} else {
result[activeRow][j] = result[activeRow][j - 1] +
result[0][j - 1]
}
}
// Print element value
fmt.Print(" ", result[activeRow][j])
back = result[activeRow][j]
}
// Change active row
if activeRow == 0 {
activeRow = 1
} else {
activeRow = 0
}
fmt.Print("\n")
}
}
func main() {
/*
row = 8
----------
1
1 2
2 3 5
5 7 10 15
15 20 27 37 52
52 67 87 114 151 203
203 255 322 409 523 674 877
877 1080 1335 1657 2066 2589 3263 4140
*/
bellTriangle(8)
}Output
1
1 2
2 3 5
5 7 10 15
15 20 27 37 52
52 67 87 114 151 203
203 255 322 409 523 674 877
877 1080 1335 1657 2066 2589 3263 4140<?php
/*
Php program for
Bell Triangle
*/
class BellNumbers
{
public function bellTriangle($row)
{
if ($row <= 0)
{
return;
}
// Optimize result by only 2 rows
$result = array_fill(0, $row + 1, array_fill(0, $row + 1, 0));
// Current row
$activeRow = 0;
// First element
$back = 1;
for ($i = 1; $i <= $row; ++$i)
{
// Previous row last element as
// first element in current row .
$result[$activeRow][0] = $back;
for ($j = 0; $j < $i; ++$j)
{
if ($j > 0)
{
if ($activeRow == 0)
{
$result[$activeRow][$j] =
$result[$activeRow][$j - 1] +
$result[1][$j - 1];
}
else
{
$result[$activeRow][$j] =
$result[$activeRow][$j - 1] +
$result[0][$j - 1];
}
}
// Print element value
echo(" ".$result[$activeRow][$j]);
$back = $result[$activeRow][$j];
}
// Change active row
if ($activeRow == 0)
{
$activeRow = 1;
}
else
{
$activeRow = 0;
}
echo("\n");
}
}
}
function main()
{
$task = new BellNumbers();
/*
row = 8
----------
1
1 2
2 3 5
5 7 10 15
15 20 27 37 52
52 67 87 114 151 203
203 255 322 409 523 674 877
877 1080 1335 1657 2066 2589 3263 4140
*/
$task->bellTriangle(8);
}
main();Output
1
1 2
2 3 5
5 7 10 15
15 20 27 37 52
52 67 87 114 151 203
203 255 322 409 523 674 877
877 1080 1335 1657 2066 2589 3263 4140/*
Node JS program for
Bell Triangle
*/
class BellNumbers
{
bellTriangle(row)
{
if (row <= 0)
{
return;
}
// Optimize result by only 2 rows
var result = Array(row + 1).fill(0).map(
() => new Array(row + 1).fill(0));
// Current row
var activeRow = 0;
// First element
var back = 1;
for (var i = 1; i <= row; ++i)
{
// Previous row last element as
// first element in current row .
result[activeRow][0] = back;
for (var j = 0; j < i; ++j)
{
if (j > 0)
{
if (activeRow == 0)
{
result[activeRow][j] =
result[activeRow][j - 1] + result[1][j - 1];
}
else
{
result[activeRow][j] =
result[activeRow][j - 1] + result[0][j - 1];
}
}
// Print element value
process.stdout.write(" " + result[activeRow][j]);
back = result[activeRow][j];
}
// Change active row
if (activeRow == 0)
{
activeRow = 1;
}
else
{
activeRow = 0;
}
process.stdout.write("\n");
}
}
}
function main()
{
var task = new BellNumbers();
/*
row = 8
----------
1
1 2
2 3 5
5 7 10 15
15 20 27 37 52
52 67 87 114 151 203
203 255 322 409 523 674 877
877 1080 1335 1657 2066 2589 3263 4140
*/
task.bellTriangle(8);
}
main();Output
1
1 2
2 3 5
5 7 10 15
15 20 27 37 52
52 67 87 114 151 203
203 255 322 409 523 674 877
877 1080 1335 1657 2066 2589 3263 4140# Python 3 program for
# Bell Triangle
class BellNumbers :
def bellTriangle(self, row) :
if (row <= 0) :
return
# Optimize result by only 2 rows
result = [[0] * (row + 1) for _ in range(row + 1) ]
# Current row
activeRow = 0
# First element
back = 1
i = 1
while (i <= row) :
# Previous row last element as
# first element in current row .
result[activeRow][0] = back
j = 0
while (j < i) :
if (j > 0) :
if (activeRow == 0) :
result[activeRow][j] = result[activeRow][j - 1] + result[1][j - 1]
else :
result[activeRow][j] = result[activeRow][j - 1] + result[0][j - 1]
# Print element value
print(" ", result[activeRow][j], end = "")
back = result[activeRow][j]
j += 1
# Change active row
if (activeRow == 0) :
activeRow = 1
else :
activeRow = 0
print(end = "\n")
i += 1
def main() :
task = BellNumbers()
# row = 8
# ----------
# 1
# 1 2
# 2 3 5
# 5 7 10 15
# 15 20 27 37 52
# 52 67 87 114 151 203
# 203 255 322 409 523 674 877
# 877 1080 1335 1657 2066 2589 3263 4140
task.bellTriangle(8)
if __name__ == "__main__": main()Output
1
1 2
2 3 5
5 7 10 15
15 20 27 37 52
52 67 87 114 151 203
203 255 322 409 523 674 877
877 1080 1335 1657 2066 2589 3263 4140# Ruby program for
# Bell Triangle
class BellNumbers
def bellTriangle(row)
if (row <= 0)
return
end
# Optimize result by only 2 rows
result = Array.new(row + 1) {Array.new(row + 1) {0}}
# Current row
activeRow = 0
# First element
back = 1
i = 1
while (i <= row)
# Previous row last element as
# first element in current row .
result[activeRow][0] = back
j = 0
while (j < i)
if (j > 0)
if (activeRow == 0)
result[activeRow][j] =
result[activeRow][j - 1] + result[1][j - 1]
else
result[activeRow][j] =
result[activeRow][j - 1] + result[0][j - 1]
end
end
# Print element value
print(" ", result[activeRow][j])
back = result[activeRow][j]
j += 1
end
# Change active row
if (activeRow == 0)
activeRow = 1
else
activeRow = 0
end
print("\n")
i += 1
end
end
end
def main()
task = BellNumbers.new()
# row = 8
# ----------
# 1
# 1 2
# 2 3 5
# 5 7 10 15
# 15 20 27 37 52
# 52 67 87 114 151 203
# 203 255 322 409 523 674 877
# 877 1080 1335 1657 2066 2589 3263 4140
task.bellTriangle(8)
end
main()Output
1
1 2
2 3 5
5 7 10 15
15 20 27 37 52
52 67 87 114 151 203
203 255 322 409 523 674 877
877 1080 1335 1657 2066 2589 3263 4140
/*
Scala program for
Bell Triangle
*/
class BellNumbers()
{
def bellTriangle(row: Int): Unit = {
if (row <= 0)
{
return;
}
// Optimize result by only 2 rows
var result: Array[Array[Int]] = Array.fill[Int](row + 1, row + 1)(0);
// Current row
var activeRow: Int = 0;
// First element
var back: Int = 1;
var i: Int = 1;
while (i <= row)
{
// Previous row last element as
// first element in current row .
result(activeRow)(0) = back;
var j: Int = 0;
while (j < i)
{
if (j > 0)
{
if (activeRow == 0)
{
result(activeRow)(j) =
result(activeRow)(j - 1) + result(1)(j - 1);
}
else
{
result(activeRow)(j) =
result(activeRow)(j - 1) + result(0)(j - 1);
}
}
// Print element value
print(" " + result(activeRow)(j));
back = result(activeRow)(j);
j += 1;
}
// Change active row
if (activeRow == 0)
{
activeRow = 1;
}
else
{
activeRow = 0;
}
print("\n");
i += 1;
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: BellNumbers = new BellNumbers();
/*
row = 8
----------
1
1 2
2 3 5
5 7 10 15
15 20 27 37 52
52 67 87 114 151 203
203 255 322 409 523 674 877
877 1080 1335 1657 2066 2589 3263 4140
*/
task.bellTriangle(8);
}
}Output
1
1 2
2 3 5
5 7 10 15
15 20 27 37 52
52 67 87 114 151 203
203 255 322 409 523 674 877
877 1080 1335 1657 2066 2589 3263 4140/*
Swift 4 program for
Bell Triangle
*/
class BellNumbers
{
func bellTriangle(_ row: Int)
{
if (row <= 0)
{
return;
}
// Optimize result by only 2 rows
var result: [
[Int]
] = Array(repeating:
Array(repeating: 0, count: row + 1), count: row + 1);
// Current row
var activeRow: Int = 0;
// First element
var back: Int = 1;
var i: Int = 1;
while (i <= row)
{
// Previous row last element as
// first element in current row .
result[activeRow][0] = back;
// Set initial value
result[0][i] = 0;
result[1][i] = 0;
var j: Int = 0;
while (j < i)
{
if (j > 0)
{
if (activeRow == 0)
{
result[activeRow][j] =
result[activeRow][j - 1] + result[1][j - 1];
}
else
{
result[activeRow][j] =
result[activeRow][j - 1] + result[0][j - 1];
}
}
// Print element value
print(" ", result[activeRow][j], terminator: "");
back = result[activeRow][j];
j += 1;
}
// Change active row
if (activeRow == 0)
{
activeRow = 1;
}
else
{
activeRow = 0;
}
print(terminator: "\n");
i += 1;
}
}
}
func main()
{
let task: BellNumbers = BellNumbers();
/*
row = 8
----------
1
1 2
2 3 5
5 7 10 15
15 20 27 37 52
52 67 87 114 151 203
203 255 322 409 523 674 877
877 1080 1335 1657 2066 2589 3263 4140
*/
task.bellTriangle(8);
}
main();Output
1
1 2
2 3 5
5 7 10 15
15 20 27 37 52
52 67 87 114 151 203
203 255 322 409 523 674 877
877 1080 1335 1657 2066 2589 3263 4140/*
Kotlin program for
Bell Triangle
*/
class BellNumbers
{
fun bellTriangle(row: Int): Unit
{
if (row <= 0)
{
return;
}
// Optimize result by only 2 rows
var result: Array < Array < Int >> = Array(row + 1)
{
Array(row + 1)
{
0
}
};
// Current row
var activeRow: Int = 0;
// First element
var back: Int = 1;
var i: Int = 1;
while (i <= row)
{
// Previous row last element as
// first element in current row .
result[activeRow][0] = back;
var j: Int = 0;
while (j < i)
{
if (j > 0)
{
if (activeRow == 0)
{
result[activeRow][j] =
result[activeRow][j - 1] + result[1][j - 1];
}
else
{
result[activeRow][j] =
result[activeRow][j - 1] + result[0][j - 1];
}
}
// Print element value
print(" " + result[activeRow][j]);
back = result[activeRow][j];
j += 1;
}
// Change active row
if (activeRow == 0)
{
activeRow = 1;
}
else
{
activeRow = 0;
}
print("\n");
i += 1;
}
}
}
fun main(args: Array < String > ): Unit
{
val task: BellNumbers = BellNumbers();
/*
row = 8
----------
1
1 2
2 3 5
5 7 10 15
15 20 27 37 52
52 67 87 114 151 203
203 255 322 409 523 674 877
877 1080 1335 1657 2066 2589 3263 4140
*/
task.bellTriangle(8);
}Output
1
1 2
2 3 5
5 7 10 15
15 20 27 37 52
52 67 87 114 151 203
203 255 322 409 523 674 877
877 1080 1335 1657 2066 2589 3263 4140Time Complexity
The time complexity of the provided code is O(n^2) where 'n' is the number of rows in the Bell Triangle. This is because for each row, we calculate the elements by adding elements from the previous row. As the number of rows increases, the number of elements to be calculated in each row increases quadratically. Therefore, the overall time complexity is quadratic.
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment