Wednesday, February 25, 2015

writing code for doing combinations

Combination is a common problem in mathematics which deals with different ways via which we can select r objects given n, where r < n. So we have n distinct objects and we can't have repetitions. For e.g., if we are to select 3 letters from the string ABCD, we have the following


ABC
ABD
ACD
BCD


So there are a total of 4 ways of selecting 3 objects.

Perfectly follows the formula,
\[{n \choose r} = \frac{n!}{r! \times (n-r)!}\]
A more simplified version of the above formula is,
\[{n \choose r}= \frac{n(n-1)(n-2)...(n-r+1)}{r!}\]
This is actually better for computations.

But how to write code to output the various selection as we've done above?

I'd take to pseudo code but you can't implement the pseudo code in one language and see the results immediately. Hence I've taken to python. I am not python-biased...I just like the simplicity of expressing logic. It models pseudo code fairly well...

There are better ways to write this...you can use a generator instead of a loop that creates and returns an array. "Generator" is a concept that is available on most of the popular programming languages. You can explore my other gists to see how this is done in python and java.

Meanwhile, happy programming.
Post a Comment