c++ - 计算排列的逆下降

Question

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

排列 A 的逆下降集是长度为 n-1 的 0-1 数组 D > 其中 D[i] = 0 如果 i+1 在 A 中 i+2 的左边否则 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 的通常下降集是长度为 n-1 的数组 D，其中 D[i] = 1 如果 A[i] > A[i+1] 和 0 否则。

因此，一种想法是计算置换的逆，然后在一次传递中采用下降集 O(n)。然而，据我所知，求逆的最佳方法仍然是 O(n^2)，所以这不会节省任何东西，但也许有更快的方法。

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

Answer 1

我认为您计算逆的方法很好，因为这可以在 O(n) 中完成。

简单地遍历 i 的每个值，从 0 到 n-1 并存储 E[A[i]]=i。

这会计算一个数组 E，其中 E[j] 给出 A[i] 在您的原始排列中的位置。