Tuesday, August 2, 2011

Factorials, Permutations, Combinations in Algorithm Design

Select/arrange/combine/group - the four keywords which bubble up in every programmer's mind. I have met people who try to solve complex algorithmic questions, but dont know the concepts behind Permutations and Combinations in Algorithm Design.

Trying to solve an algorithm for permutation or combination, without knowing the fundamentals is like convincing a girl for a night out without knowing what/when/where/how to do it ;)

So, here I'll cover all the concepts which won't let you in that situation ;)

Lets go through them one by one.

What is factorial:

Factorial n = n * (n-1) * (n-2) *... * 2 * 1

Ok, got it. I know this. I studied that in school. But, where does it come into Algorithm Design.

Think about this -

There are 13 cards, from 2 to A: 2, 3, 4, 5, 6, 7, 8, 9, 10, J, Q, K, A. We can arrange the 13 playing cards in a variety of orders, without removing any card. Factorial of 13 or 13!

There are 6 companies. In how many ways they can be merged. Answer: 6!

Factorial is about arranging/selecting "all" the available items (n out of n), without any duplicate arrangements.

Example: in how many ways 1,2,3 be arranged.
Answer: !3 = 3 * 2 * 1 = 6 ways.

123, 132, 213, 231, 312, 321

Now lets move on to the next level.

What is Permutation:

Yes, the order does matter!

Selecting/Arranging r items out of m, in problems where order does matter.
n P r  or P(n,r) = n! / (n - r)!

When order matters   AB != BA.

Now Suppose we want to take these four people and arrange them in groups of three at a time where order matters.   The following demonstrates all the possible arrangements from B,A,M,S

BMS,    BSM,    BAS,   BSA,   BMA,    BAM
MBS,    MSB,    MAS,   MSA,   MBA,    MAB
SBM,    SMB,    SBA,   SAB,   SMA,    SAM
ABM,    AMB,    ABS,   ASB,   AMS,    ASM

There are 24 ways to arrange 4 objects taken 3 at a time.

There are !6/!(6-4) = !6/!2 = 360 ways to arrange 6 items taken 4 at a time when order matters.

Note:
nPn = !n/!0 = !n
There are n! ways to arrange n objects in groups of n at a time. And this is what is Factorial.

Now what if the order was not important? Lets see that.

What is Combination:

A combination is one of the different arrangements of a group of items where order does not matter, taking r elements out of n.

My fruit salad is a combination of apples, grapes and bananas.

When order does not matter   AB = BA.

n C r  or C(n,r) = !n/(!r * !(n - r))

Take 4 people and place them in groups of 3 at a time where order does not matter = C(4,3)

Select a subcommittee of 7 members from among a committee of 17 = C(17,7)

Thats it! Remember these concepts while trying for an algorithm involving select/arrange/combine/group. It helps alot to throughly get into the problem statement.