algorithm - 将排列转换为反转表示

Question

前 N 个自然数的

排列 P = [a1, a2, ... , aN] 可以用 inversions 的列表表示I = [i1, i2, ... , iN]，其中 iK 告诉我们可以找到多少个大于 K 的数在排列 P 中的 K 之前。

示例:如果 P = [3, 1, 4, 2]，则 I = [1, 2, 0, 0](3 放在 1， 3 和 4 放在 2 之前，而 3 和 4 前面没有任何更大的数字)。

有一个明显的算法，将一个排列从标准形式转换为反转形式，并在 O(N^2) 中运行(我们只是按照定义和计数)。这同样适用于反向转换(稍微不那么直接)。

Is there an algorithm that has lower time complexity?

Answer 1

有一个简单的迭代动态规划算法可以解决这个问题:对于从 1 到 n(排列的长度)的所有 i，取数字 i 看看如何i 左侧的 P 中的许多元素已经出现。由于我们按升序处理 i，我们知道 未 看到的元素是比 i 大的元素 - 因此我们计数并记下这些元素的数量。诀窍是引入一个外部列表，而不是跟踪 P 中的哪些元素已经被看到。

首先，让我们看看如何以O(n^2) 的方式进行。例如，如果 P=[4, 3, 2, 1]，则算法执行如下:

1. 创建一个初始化为零的结构树。如果迭代算法已经看到 P 中第 j 个位置的元素，它在位置 j 中保持“1”。

2. 取1，确定pos==3。在 tree[pos] 中写下“1”。计算等于 0 的 num_seen=sum(tree[0:3])。在 I[0] 处写下 pos - num_seen + 1 >。之后:tree = [0, 0, 0, 1], I = [3, 0, 0, 0]

3. 取 2，在树 [1] 中写下“1”，在 I[1] 中写下 1。 树 = [0, 1, 0, 1], I=[3,1,0,0]。

4. 取 3，在 tree[2] 中写下“1”，在 I[2] 中写下 0。 树 = [0, 1, 1, 1], I=[3,1,0,0]。

5. 取 4，在树 [0] 中写下“1”，在 I[3] 中写下 0。 树 = [1, 1, 1, 1], I=[3,1,0,0]。

第二个技巧是使用高效的数据结构来计算在 O(n log n) 时间而不是 O(n^2) 中看到的元素的数量> 如上所述。

这是使用 Fenwick 树快速计算已见元素数量的 Python 代码:

def ft_sum(tree, a, b):
  if a == 0:
      s = 0;
      while  b >= 0:
          s += tree[b];
          b = (b & (b + 1)) - 1
      return s
  return ft_sum(tree, 0, b) - ft_sum(tree, 0, a - 1)

def ft_adjust(tree, k, v):
    while k < len(tree):
        tree[k] += v
        k |= k + 1

def calcI(P):
    n = len(P)
    tree = [0] * n
    I = [0] * n
    positions = [0] * n
    for i in xrange(n):
        positions[P[i]-1] = i
    tree = [0] * n
    for i in xrange(n):
        pos = positions[i]
        ft_adjust(tree, pos, 1)
        num_seen = ft_sum(tree, 0, pos)
        I[i] = pos - num_seen + 1
    return I