computing inverse descents of permutations

Question

A permutation of n is an array A of length n containing entries 1,2,...,n each once.

The inverse descent set of a permutation A is a 0-1 array D of length n-1 where D[i] = 0 if i+1 is to the left of i+2 in A and otherwise D[i] = 1.

Examples (n=4):

[1, 2, 3, 4] [0, 0, 0]
[1, 2, 4, 3] [0, 0, 1]
[1, 3, 4, 2] [0, 1, 0]
[2, 3, 4, 1] [1, 0, 0]
[1, 3, 2, 4] [0, 1, 0]
[2, 3, 1, 4] [1, 0, 0]
[1, 4, 2, 3] [0, 0, 1]
[1, 4, 3, 2] [0, 1, 1]
[2, 4, 3, 1] [1, 0, 1]
[3, 4, 2, 1] [1, 1, 0]
[2, 1, 3, 4] [1, 0, 0]
[3, 1, 2, 4] [0, 1, 0]
[4, 1, 2, 3] [0, 0, 1]
[2, 1, 4, 3] [1, 0, 1]
[3, 1, 4, 2] [0, 1, 0]
[2, 4, 1, 3] [1, 0, 1]
[3, 4, 1, 2] [0, 1, 0]
[3, 2, 1, 4] [1, 1, 0]
[4, 2, 1, 3] [1, 0, 1]
[4, 3, 1, 2] [0, 1, 1]
[3, 2, 4, 1] [1, 1, 0]
[4, 2, 3, 1] [1, 0, 1]
[4, 1, 3, 2] [0, 1, 1]
[4, 3, 2, 1] [1, 1, 1]

The naive way to compute the inverse descent set of a permutation is O(n^2). I'd really like something faster. Here's the naive thing

for (int i=0; i<n-1; ++i) {
  for (int j=i+1; j<n; ++j) {
    if (A[j] == i+2) {
      D[i] = 1;
      break;
    } else if (A[j] = i+1) {
      D[i] = 0;
      break;
    }
  }
}

This is called an inverse descent because it's what you get if you take the inverse of the permutation and then take the usual descent set. The usual descent set of a permutation A is an array D of length n-1 where D[i] = 1 if A[i] > A[i+1] and 0 otherwise.

Therefore one idea is to compute the inverse of the permutation, then take the descent set in one pass O(n). However, the best way that I know to take the inverse is still O(n^2), so that doesn't save anything, but maybe there's a faster way.

I'm writing in C++, but any pseudocode solution would be great.

Answer 1

I think your approach of calculating the inverse is good as this can be done in O(n).

Simply loop over each value of i from 0 to n-1 and store E[A[i]]=i.

This computes an array E where E[j] gives the location of A[i] in your original permutation.