Algorithms
Permutation Rank
Find the rank of a number in the lexicographic order of its permutations
For example: 312 has rank 5 in the sorted permutation list {123, 132, 213, 231, 312, 321}. A brute force method would be to generate all the permutation and sort them. This will be in exponential order as to generate all the permutation.
lets do it efficiently. Suppose given number X=415. We only consider the digits in order i.e. :{4,5,1}
Lets assume that it is of rank=1. But it is not!
If we want to fix 4 at position 0 then we need to increase the rank by number of permutations of {4, 1, 5} starting with an element less than 4. We have only 1 such element i.e. {1}. With 1 at position 0 we can have 2! permutations.
so, rank += 1X2! = 1+2 = 3
Let’s fix 4 at position 0 and move our focus to position 1 with remaining elements {1, 5}. In order to fix 5 at position one we need to increase rank by number of permutations of {1, 5} starting with an element less than 5. Again {1} is such an element. With 4 fixed at position 0 and 1 at position 1 we have 1! permutations.
so, rank += 1X1! = 3+1 = 4
Lets fix 5 at position 1 and focus on position 2 with remaining elements {1}. In order to fix 1 in position 3 we need to increase rank by number of permutations starting with less than 1. We have no such element. So, with 45 fixed at first two positions and 1 at position 3 we have : 0! permutations
so, rank+=0X0! = 4+0 = 4.
Here is a code for above algorithm. It runs O(n^2) as finding smaller count on right is O(n^2). We can make it O(nlgn) if we use inversion count to count smaller on right in O(nlgn). Checkout my previous post here. Also we can use AVL tree to find the smaller element count on right. Check my previous post Count smaller on right to get it done in O(ngln).
public static int[] smallerCountOnRight(final int[] X) {
int[] smaller = new int[X.length];
for(int i = 0; i < X.length; i++){
for(int j = i+1; j < X.length; j++){
if(X[j] <= X[i]){
smaller[i]++;
}
}
}
return smaller;
}
public static int permRank(final int[] X) {
final int[] smaller_count = countSmallerOnRightWithMerge(X);
final int[] factorial = new int[X.length];
factorial[0] = 1;
factorial[1] = 1;
for (int i = 2; i < X.length; i++) {
factorial[i] = i*factorial[i - 1];
}
int rank = 1;
for (int i = 0; i < X.length; i++) {
rank += smaller_count[i] * factorial[X.length - i - 1];
}
return rank;
}
Count Smaller On Right
Checkout my previous post (using inversion count) for details. I am hereby describing the one using inversion count.
public static void mergeToCountSmallerOnRight(int A[], int rank[], int p, int q, int r, int count[]){
int n = r-p+1;
int i = p;
int j = q+1;
int mid = q;
int k=0;
int mergedRank[] = new int[n];
int smallerCount = 0;
while(i <= mid && j <= r){
//satisfies i<j, A[i]<A[j] -- so this is the end of smaller counts so far for A[i]. update smaller count.
if(A[rank[i]] < A[rank[j]]){
count[rank[i]] += smallerCount;
mergedRank[k++] = rank[i++];
}
//i<j, A[i]>=A[j] -- smaller element found for A[i], incr count
else{
smallerCount++;
mergedRank[k++] = rank[j++];
}
}
//copy leftovers from the two partitions into merge
while(i <= mid){
count[rank[i]] += r-q;
mergedRank[k++] = rank[i++];
}
while(j <= r){
mergedRank[k++] = rank[j++];
}
//update rank
System.arraycopy(mergedRank, 0, rank, p, n);
}
public static void countSmallerOnRightWithMerge(int A[], int rank[], int p, int r, int count[]){
if(A.length == 1){
return;
}
if(p < r){
int q = (p+r)/2;
//sort left side and count ic
countSmallerOnRightWithMerge(A, rank, p, q, count);
//sort right side and count ic
countSmallerOnRightWithMerge(A, rank, q+1, r, count);
//merge left and right and count cross ic
mergeToCountSmallerOnRight(A, rank, p, q, r, count);
}
}
public static int[] countSmallerOnRightWithMerge(int A[]){
int n = A.length;
int[] rank = new int[n];
int count[] = new int[n];
for(int i = 0; i < n; i++){
rank[i] = i;
}
countSmallerOnRightWithMerge(A, rank, 0, n-1, count);
return count;
}