ginaspider (ginaspider) wrote in algorithms,
ginaspider
ginaspider
algorithms

I'm not terrible keen on understanding Gaussian coefficients at the moment. I just want to generate them. Does anyone know of an algorithm that does this or know the pattern they have? EG:

1,1
1,2
1,3
1,4,6
1,5,10
1,6,15,20
1,7,21,35
1,8,28,56,70
.. etc
  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 9 comments
Look at this:

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
...

Basically, every number is the sum of the two above it. One possible function to generate them could be: c(i,j) = c(i,j-1) + c(i-1, j-1), with appropiate definitions of i and j.

Oops. I actually formatted it symmetrically, but it didn't work. I should try some html next time.
ok, huh. I see now. Thanks!

madcaptenor

April 29 2008, 20:14:51 UTC 7 years ago Edited:  April 29 2008, 20:15:28 UTC

That algorithm's fine, but even if you use dynamic programming (that is, remember the values of c(i,j) you've already computed, instead of recomputing them every time the recursion calls for one) that would take time O(i^2) to compute c(i,j). (Basically, you have to generate the entire first i rows of the triangle.)

There's a faster algorithm to compute binomial coefficients; it takes O(j) time.
Ok, thank you.
For row i (where 1,1 is the i=1 row) and column j (where 1 is the j=0 column) we also have:

c(i,j) = Π( ((k+1)-j)/j ) from k=0 to i -- j &neq; 0
c(i,j) = 1 -- j = 0

e.g.
c(8,5) = (9-1)/1 * (9-2)/2 * (9-3)/3 * (9-4)/4
c(8,5) = 8*(7/2)*2*(5/4)
c(8,5) = 70

For an implementation you'd obviously want to multiply by ((k+1)-j), then divide, else you could get into FP issues.
OR: What madcaptenor said.

(That'll teach me to not refresh a comment window ten minutes after opening it.)
a wise man once said, "understanding is the key to generation." or something along those lines.
O hai. So this code looks funny but works in practice:

int *gauss_coef;

void tack_line(int offset, int depth) {
 int a, b, k;
 for(k = 0;k< depth; k++) {
   if(  (offset - (depth -1 ) + k) == offset) 
   a = 0;
  else
   a = gauss_coef[offset - (depth-1) + k];
  if( (offset - (depth-1) +k -1) < (offset - (depth-1)))
   b = 0;
  else
   b = gauss_coef[offset - (depth-1)+k-1];
  gauss_coef[k+offset] = a+b;
 } 
}

void build_coef(int depth) {
 int i,j, k;
 j = 0;
 for(i = 0;i<depth;i++)
  j+=i;
 gauss_coef = (int *)malloc(j * sizeof(int));
 gauss_coef[0] = 1;

 j = 1;
 for(i = 2; i< depth;i++) {
  tack_line(j, i);
  j+=i;
 }
}