Calculation of reverse descents of permutations

Question

The permutation n is an array A length n containing entries 1,2,...,n each time.

The reverse set of descent descent A is an array 0-1 D length n-1 , where D[i] = 0 if i+1 is to the left of i+2 in A , 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] 

A naive way of calculating the reverse descent of a set of permutations is O(n^2) . I would really like something faster. Here is a 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 reverse descent because this is what you get if you take the inverse of the permutation and then take the regular descent set. The usual set of descent descent A is an array D length n-1 , where D[i] = 1 if A[i] > A[i+1] and 0 otherwise.

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

I write in C ++, but any pseudo-code solution would be great.

Answer 1

This can be done in O (n).

Each D[i] indicates whether the first character was i+1 or i+2 . Therefore, for each A[i] update D[A[i] - 1] and D[A[i] - 2] (update only one of them for edge cases), set the element (s) accordingly.

For example [4,1,3,2] :

 4 => D[2] is unset so D[2] := 1 1 => D[0] is unset so D[0] := 0 3 => D[1] is unset so D[1] := 1; D[2] is already set 2 => D[1] is already set; D[0] is already set D = [0,1,1] 

the code:

 //Initialize all elements of D to something other than 0 or 1; for example, 2. for (int i=0; i<n; ++i) { // edge cases if (A[i] == 1 && D[0] == 2){ D[0] = 0; } else if (A[i] == n && D[n - 2] == 2){ D[n - 2] = 1; // everything else } else { if (D[ A[i] - 2 ] == 2){ D[ A[i] - 2 ] = 1; } if (D[ A[i] - 1 ] == 2){ D[ A[i] - 1 ] = 0; } } } 

Answer 2

I think your approach to computing inverse is good, as it can be done in O (n).

Just loop each value of i from 0 to n-1 and save E[A[i]]=i .

The array E calculated here, where E[j] indicates the location of A[i] in the original permutation.