Posted on by Kalkicode
Code Dynamic Programming

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:

  1. Start with an empty 2D array result to store the Bell Triangle elements.
  2. Initialize activeRow to 0 to indicate the current row we are filling, and back to 1 as the initial value for the first element.
  3. For each row i from 1 to the desired number of rows: a. Set the first element of the current row (result[activeRow][0]) to the value of back. 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. Update back to the last element of the current row (result[activeRow][j]). e. Switch the value of activeRow between 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  4140
package 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  4140

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

Comment

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