/** Solution for "9 billion names of God the integer" task on RosettaCode: http://rosettacode.org/wiki/9_billion_names_of_God_the_integer */ class PartitionCount { // Array of elements. triangle@row@col is the number of partitions of row // have col as the largest element. Conversely, it is ALSO the number of // partitions of row into exactly col parts. class var triangle = [[0],[0,1]] // Array of cumulative sums in each row. class var sumTriangle = [[1],[0,1]] class calcRowsTo[toRow] := { for row = length[triangle] to toRow { triangle@row = workrow = new array[[row+1],0] sumTriangle@row = sumworkrow = new array[[row+1],0] oversum = 0 for col = 1 to row { otherRow = row-col sum = sumTriangle@otherRow@min[col,otherRow] workrow@col = sum oversum = oversum + sum sumworkrow@col = oversum } } } class rowSum[row] := { calcRowsTo[row] return sumTriangle@row@row } } PartitionCount.calcRowsTo[25] for row=1 to 25 { for col=1 to row print[PartitionCount.triangle@row@col + " "] println[] } // Test against Frink's built-in much faster partitionCount function that uses // Euler's pentagonal method for counting partitions. testRow[row] := { sum = PartitionCount.rowSum[row] println["\$row\t\$sum\t" + (sum == partitionCount[row] ? "correct" : "incorrect")] } println[] testRow[23] testRow[123] testRow[1234] testRow[12345]