## Archive for May, 2009

## Calculating Combinatorials

Posted on May 29, 2009, under general.

A question came up recently, over at RedBrick, about how to efficiently calculate very large combinatorials. A combinatorial of the form:

c = N! / (k! * (N - k)!)

describes how many combinations (c) there are if you pick k items out of N. For example if you pick 5 people at random out of a team of 10, there are 252 potential combinations. A straight forward code implementation of the formula looks like:

1 2 3 4 5 6 7 8 | def fact(n, acumulator=1): if not n: return acumulator else: return fact(n - 1, acumulator * n) def combinatorial(n, k): return fact(n) / fact(k) / fact(n - k) |

But this is very inefficient, each call to factorial is O(N). Surprisingly, google couldn’t find any clear alternatives, so to fix that, here is the more efficient way to calculate it:

1 2 3 4 5 | def combinatorial(n, k): c = 1 for i in range(k + 1, n + 1): c *= float(i) / (i - k) return c |

This implementation runs in O(N-K), which is at least 3 times faster than the initial implementation and usually much more so.

Here’s how it works;

First, re-organise the formula as:

c = ((N!) / (k!)) / (N -k)!

Next, it should be obvious that N! / k! is the same thing as N * N – 1 * N – 2 * … k + 1. So we construct our loop to compute that:

1 2 3 | c = 1 for i in range(k + 1, n + 1): c *= i |

but we still need to divide by (N – k)!. We already have a for loop, of exactly that number of iterations, so we can reuse it. (N – K)! is the same thing as SUM(i – k) , as we iterate i. Since division and multiplication are commutative in this context, and the order never matters we place the division directly in-line within the loop. Lastly, since we’re now dividing, we might end up with fractions at intermediary stages, so we use floating point.

1 2 3 | c = 1 for i in range(k, n): c *= float(i) / (i - k) |

Another great property of these kinds of operations is that are they partitionable, if we have W workers, we can give each (N – K) / W values to compute, and then multiply their respective answers. But I’ll leave that as an exercise for the reader.

## Blasphemy in a nutshell

For reasons best understood by our Minister for Justice (who seems to be going it alone on this one) Ireland may shortly introduce a new offence of blasphemous libel. The Irish blogosphere, and twitter are both alight with incandescent disapproval.

I’m not entirely sure what to make of the proposal. I think it’s an amazingly dumb idea, not only for the straight-forward civil rights reasons, but also because I can’t see the courts or anybody else implementing it in the real world. It is political tokenism in its most bare, stupidest, form.

Normally, I’m not one to set out to offend people … live and let live, I say. But faced with only limited amount of time to safely go on the record on the topic, here’s my own summary of roughly where the major beliefs (that I’ve read enough about to have an opinion on) are in relation to each other:

Don’t take it too seriously … it’s just an approximate summary from my own personal musings. Though it’s not arbitrary, I can back it all up.

I do happen to think that it’s a lot more likely that aliens exist than, say … angels. Pantheism is less contradictory than atheism, because at least the former can ascribe the existence of the universe to “Um, magic” with a straight face. The Abrahamic religions naturally get progressively more insane, as they inherit myths and superstitions from each other. And Quakers, well, they just make the nicest cereals. Mormonism? see the Golden Plates.

Saying that a religion or belief is “bad” or “good” is nonsense. Christianity and Islam, for example, are brilliant wonderful positive movements for good. They encourage great values and positive work. But at the same time, they can be a force for harm. Major branches discourage life-saving devices like condoms and deny many rights to women. Hence the spread between both good, and evil. I’ve trended them more towards evil only because of the dark ages and the stifling effects on the progress of mankind.

### Disclaimer:

Though it shouldn’t need to be said; the above is mainly *humour*. The categories are waaaaaay too broad. The comparison completely ignores any implicit value faith may have (for its own sake) and the scales are unscientific. Sanity or insanity shouldn’t be inferred upon any actual practitioners (Except maybe Richard Dawkins, who might be both non-contradictory *and* a little insane), these are just big rough averages.

If you’re happy with your beliefs, than I am happy for you. If you support the idea that blasphemy should be illegal, get a life.