计算排列的逆下降

Question

排列n是一个A长度数组,每个n包含1,2,...,n一次条目.

逆下降集的置换的A是0-1阵列D的长度n-1,其中D[i] = 0,如果i+1是左侧i+2的A以及以其他方式D[i] = 1.

例子(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]

计算置换的逆下降集的天真方法是O(n^2).我真的很喜欢更快的东西.这是天真的事情

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;
    }
  }
}

这被称为反向下降,因为如果你采用排列的倒数然后采用通常的下降集,那就是你得到的.排列的通常下降集A是D长度的数组,n-1其中D[i] = 1if A[i] > A[i+1]和0否则.

因此,一个想法是计算置换的逆,然后在一遍中取下降集O(n).然而,我知道采取逆转的最好方法仍然是O(n^2),所以不能保存任何东西,但也许有更快的方法.

我正在用C++编写,但任何伪代码解决方案都会很棒.

Answer 1

这可以在 O(n) 内完成。

每个D[i]代表是否i+1或i+2已被首先看到。因此，对于每个A[i]，更新D[A[i] - 1]并D[A[i] - 2]（对于边缘情况仅更新其中之一），适当地设置元素。

例如[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]

代码：

//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;
    }
  }
}