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++ 编写,但任何伪代码解决方案都很棒。
最佳答案
我认为您计算逆的方法很好,因为这可以在 O(n) 中完成。
简单地遍历 i
的每个值,从 0 到 n-1 并存储 E[A[i]]=i
。
这会计算一个数组 E
,其中 E[j]
给出 A[i]
在您的原始排列中的位置。
关于c++ - 计算排列的逆下降,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/25274369/