Pascal's Triangle generator

• Monday, 11 Jan 2010
• code • triangle • generator • personal • english • it • pascal • optimization • memory • cool
• 417 words

What’s Pascal’s Triangle? That’s what it is (Wikipedia has all the theory, if you need).

Pascal's Triangle first 6 rows

The thing I wrote here is a generator of the n-th row of the triangle, that doesn’t use more then the memory needed to store the solution. Instead of allocating a Triangular Matrix, and building every row based on the one above, solution is built in place.

How does it work

The result is generated “filling the row from right to left”. I start initiating the element on the right hand side to '1'. Then, I run something like:

init result[0.. requested_row]

result[requested_row-1] = 1

for i = 2 -> requested_row do:
   for j = requested_row-i -> requested_row-1 do:
      result[j] = result[j] + result[j+1]
   endfor
endfor

Clearly this is nothing special. Just a little trick to avoid to use a triangular matrix. Memory is not cheap, you know! ;-)

#include <stdio.h>
#include <stdlib.h>

void print_row(unsigned long long* row, unsigned int size) {
    static unsigned int j;
    for ( j = 0; j < size; ++j ) { printf("%llu ", row[j]); }
    printf("\n");
}

unsigned long long* pascal_triangle_line(unsigned int pascal_row){
    static unsigned int i, j;
    unsigned long long* result = NULL;
    result = (unsigned long long*)calloc(pascal_row, sizeof(unsigned long long));
    
    if ( NULL != result ) {    
        result[pascal_row-1] = 1; // First element on the right is always '1'
        for ( i = 2; i <= pascal_row; ++i ) {
            
            #ifdef DEBUG
            print_row(result, pascal_row);
            #endif
            
            for ( j = pascal_row-i; j < pascal_row-1; ++j ) {
                result[j] += result[j+1]; // Calculate the 'j'-th element
                
                #ifdef VERBOSE
                printf("(row: %d, element: %d) => %llu\n", i, j, result[j]);
                #endif
            }
        }
    }
        
    return (result);
}

int main(int argc, char** argv)
{
    unsigned int input;
    unsigned long long* result = NULL;
       
    // Check the Input
	if ( argc == 2 ) input = atoi(argv[1]); else return (EXIT_FAILURE);
    
    // Calculate the required line
    result = pascal_triangle_line(input);
    
    // Print result
    if ( NULL != result ) { 
        printf("RESULT ROW:\n");
        print_row(result, input);
        return (EXIT_SUCCESS);
    }
    return (EXIT_FAILURE);
}

Complexity in time: O(n²/2). After all, the complexity is a constant operation O(1), multiplied by the number of elements in the Triangular Matrix: n² elements divided by 2. BUT bear in mind that O(n²/2) = O(n²). So, it’s more correct to say that the complexity is quadratic.

Of course, if instead you need the whole triangle (not just an arbitrary row) you will have to store it somewhere, so this solution wouldn’t work for you as it is.