The Most Excellent Bell Number Problem (by Chris Bell)

It turns out that Mr. Bell has a formal, mathematical entity named after him. It is called the Bell Triangle. It is obviously superior to Pascal's Triangle; please don't waste our time by trying to argue the point.

Here are the first seven rows of a Bell Triangle:

[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]

Because this is computer science, we will start the counting from zero. The zeroth row contains a one. Each subsequent row is filled with these two rules:

• The zeroth element in a row is the last element from the previous row.
• Every subsequent element is the sum of the element to its left and the element to its left and up one row.

We will use the notation B_row,column to mean the Bell number from that row and column. B_3,2 is 10 because to its left is a 7 and to its left and up is a 3. (Remember, we start counting rows and columns from zero!)

1. Write the method bellRow() that takes an integer input and returns that row of the Bell Triangle. The row should be in the form of an ArrayList<Integer>.

Example:

System.out.println(bellRow(0));    // prints [1]
System.out.println(bellRow(3));    // prints [5, 7, 10, 15]
System.out.println(bellRow(6));    // prints [203, 255, 322, 409, 523, 674, 877]

Important Thought #1: Two ArrayLists, not one, are recommended for solving this problem. (Why?)

Important Thought #2: There is a method called clone which can be used to copy one ArrayList to another. It is not essential for this problem, but it may be useful.

2. Write the method bellNum() that takes two integer inputs, a row and a column, and returns the element from that row and column in a Bell Triangle.

System.out.println(bellNum(0,0));  // prints 1
System.out.println(bellNum(3,2));  // prints 10
System.out.println(bellNum(6,3));  // prints 409

	
	public static ArrayList<Integer> bellRow(int n) {
		ArrayList<Integer> previous = new ArrayList<Integer>();
		ArrayList<Integer> current = new ArrayList<Integer>();
		previous.add(1);

		for (int i = 0; i < n; i++) {
			current.add(previous.get(previous.size()-1));
			for (int j = 0; j < previous.size(); j++) {
				current.add(current.get(j) + previous.get(j));
			}

			// Two choices here...
			// VERSION 1 (commented out)
			//
			// One way to do this is to use clone() to make a copy of the current ArrayList
			// Because previous and current are therefore referencing different ArrayLists in
			// memory, clearing current will have no bearing on previous
//			previous = (ArrayList<Integer>) current.clone();
//			current.clear();

			// VERSION 2 (not commented out)
			// Another way to do this is to set previous to the current row's memory location.
			// If this is done, then any changes that reference current's memory location will
			// be reflected in previous since they are literally the same.  This means that
			// current.clear() will also clear previous, so that is not an option.  However,
			// creating a new ArrayList in memory and assigning that new location to current
			// will not change the data or location that previous now refers to, but it will
			// change the location to which current does.  Since that new memory location refers
			// to an empty list, we get the effect of clearing current.
			previous = current;
			current = new ArrayList<Integer>();

			// Only one version should be commented out for this to work.
		}
		
		return previous;
	}
	
	// The second problem is straightforward when using of bellRow
	public static int bellNum(int row, int column) {
		return bellRow(row).get(column);
	}