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:

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.

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.)

karinfromnosundApril 29 2008, 19:41:24 UTC 7 years ago

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.

karinfromnosundApril 29 2008, 19:44:34 UTC 7 years ago

ginaspiderApril 29 2008, 20:02:29 UTC 7 years ago

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

There's a faster algorithm to compute binomial coefficients; it takes O(j) time.

ginaspiderApril 30 2008, 03:22:42 UTC 7 years ago

nekokazeApril 29 2008, 20:24:15 UTC 7 years ago

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.

nekokazeApril 29 2008, 20:25:34 UTC 7 years ago

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

arvindnApril 30 2008, 04:47:56 UTC 7 years ago

ginaspiderNovember 25 2008, 04:01:13 UTC 7 years ago

ginaspiderwrote inalgorithms: ←raytracerantilamerwrote inalgorithms: →Category theory and query optimization