Rank permutation with increasing runs and constraints

Viewed 82

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;
}
0 Answers
Related