Category Archives: Permutations

Ambiguous permutations

Given a permutation of numbers from 1 to N, We can represent it in two ways.

For example, let us consider a permutation from 1 to 5
P = [2 4 1 5 3]
This representation directly indicates the position of each number. i.e 2 is first, 4 is second and so on.

Alternatively, this can also be represented in inverse permutation form.
A = [3 1 5 2 4]
Assuming 1-based index, each number at the index ‘i’ indicates that the number ‘i’ is positioned at A[i] in the actual permutation. So this means that 1 appears at index 3, 2 appears at index 1, and so on.

There are some cases when the actual permutation and the inverse permutation are same. We call it as an ambiguous permutation. Now the problem is how do we check if the give permutation is an ambiguous permutation?

The solution is simple. We have to create an inverse permutation in another array, and check if it is same as the original permutation. Calculating the inverse permutation is discussed in my previous post.

Following is the C++ code. It runs in O(n) time and O(n) space.

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