I want to rank permutations which have serveral increasing runs. A increasing run is a sequence of permutation elements in the following form perm[i] < perm[i+1]. The constraint is that perm[i+1] - perm[i] <= maxDistance inside increasing runs. A turningpoint at index i describes following: perm[i-1] > perm[i].
Example 1234, maxDistance = 2, turning point at index 2
Valid permutations:
1324,2413,3412
Invalid permuations:
1423 greater MaxDistance
1243 turning point at index 3
Here is my attempt: which gives me rank 1 for 1324, rank 3 for 2413, rank 4 for 3412 but ranking starts with 0. But i dont know why the ranks are not 0,1,2. How can i rank this kind of permutations? Thank you in advance.
public BigInteger calcRank(int[] perm, int maxDistance){
BigInteger rank = BigInteger.ZERO;
BigInteger multipler = BigInteger.ONE;
List<Integer> turns = calcTurns(perm);
int[] numbers = getNumbers(perm.length);
for(int j=0,last=-1,q=0;j<perm.length && j<turns.get(turns.size()-1);j++){
int all=0;
int avail=0;
if(j == turns.get(q)){
for(int l=0;l<numbers.length;l++){
if(numbers[l] != -1){
last = l;
break;
}
}
q++;
}
for(int k=last,org=last;k < numbers.length;k++){
if(numbers[k] == -1){
continue;
}
if(all == maxDistance || numbers[org]+maxDistance < numbers[k]){
break;
}
if(numbers[k] == perm[j]){
avail = all;
numbers[k] = -1;
for(int l=k+1;l<numbers.length;l++){
if(numbers[l] != -1){
last = l;
}
}
}
all++;
}
rank = rank.add(multipler.multiply(BigInteger.valueOf(avail)));
multipler = multipler.multiply(BigInteger.valueOf(all));
}
return rank;
}
private List<Integer> calcTurns(int[] perm){
List<Integer> out=new ArrayList<>();
out.add(0);
for(int i=1;i<perm.length;i++){
if(perm[i-1] > perm[i]){
out.add(i);
}
}
return out;
}
private int[] getNumbers(int n){
int[] out = new int[n];
for(int i=1; i <= n;i++){
out[i-1] = i;
}
return out;
}