ginaspider (ginaspider) wrote in 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

karinfromnosund

April 29 2008, 19:41:24 UTC 6 years ago

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.

karinfromnosund

April 29 2008, 19:44:34 UTC 6 years ago

Oops. I actually formatted it symmetrically, but it didn't work. I should try some html next time.

ginaspider

April 29 2008, 20:02:29 UTC 6 years ago

ok, huh. I see now. Thanks!

madcaptenor

April 29 2008, 20:14:51 UTC 6 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.

ginaspider

April 30 2008, 03:22:42 UTC 6 years ago

Ok, thank you.

nekokaze

April 29 2008, 20:24:15 UTC 6 years ago

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.

nekokaze

April 29 2008, 20:25:34 UTC 6 years ago

OR: What madcaptenor said.

(That'll teach me to not refresh a comment window ten minutes after opening it.)

arvindn

April 30 2008, 04:47:56 UTC 6 years ago

a wise man once said, "understanding is the key to generation." or something along those lines.

ginaspider

November 25 2008, 04:01:13 UTC 5 years ago

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;
 }
}