Monday, December 22, 2014

Number of ways of arranging 0, 1

Given 'N' zeros and 'M' ones, In how many ways can we arrange them to form a string of length (N+M)?

For example if we have 2 zeros and 2 ones, we can arrange them in 6 ways
0011, 1100, 0101, 1010, 1001, 0110

If there are N symbols to arrange, The number of ways to arrange them in a sequence is called a permutation problem. This number is simply N! (N factorial).

We have (N+M) symbols in total and N symbols are one type and M symbols are another type, So the number of permutations become (N+M)!/ N!*M!

Another way to look at the problem is using combinations. We have (N+M) places either
  • We have to choose N spaces to fill zeros, in the remaining places, we fill one
  • Or We have to choose M spaces to fill ones, in the remaining places, we fill zero
The number of ways to choose R objects from N objects is called a combination problem. This is represented by C(N,R) = N!/(N-R)!*R!

So for our problem there are (N+M) symbols and we need to either choose N zeros or M ones. So it becomes C(N+M,N) or C(N+M,M)

Both reduce to (N+M)!/N!*M!.

If we try to implement the above formula as it is in code, we have a problem of data overflow.

For example consider 21! = 51090942171709440000, we cannot represent in a long integer also. If we are calculating C(21,10), simply calculating factorials with built in data types result in data overflow even though the result can be represented in those types. C(21,10) = 352716.

In competitive programming, it is sometimes asked to reduce this value using a modulo operation. For example calculate C(n,r) modulo 10007 for arbitrarily large numbers say 1 <= n,r <= 1000. In these cases also, using the factorial formula does not serve the purpose.

We have another formula to calculate C(N,R) using recursive definition.
C(N, R) = C(N-1, R-1) + C(N-1, R)
You can easily understand this by using Pascal triangle.
If we implement the algorithm using this formula, we can find the result for a much better range of numbers .

Here is the Java implementation. For this problem I assumed the range of 1000 for N and M. Also it calculates the result modulo 109+7