将排列转换为反转表示

Question

第一个N自然数的P = [a1, a2, ... , aN]排列可以用inversionsI = [i1, i2, ... , iN]的列表表示，其中iK告诉我们有多少个数字在 P.

排列中，可以在 K 之前找到大于 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

有一个简单的迭代 dynamic-programming 算法可以解决这个问题：对于从 1 到 n（排列的长度）的所有 i，取数字 i 并查看有多少个元素在 P 左边 i 已经看到了。由于我们按递增顺序处理 i，我们知道 未看到的元素 是大于 i 的元素 - 因此我们计算并记下那些元素。诀窍是引入一个外部列表，而不是跟踪 P 中的哪些元素已经被看到。

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

创建一个初始化为零的结构tree。如果迭代算法已经看到 P 中具有 j-th 位置的元素，则它在位置 j 中保持“1”。
取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]
取2，在树[1]中写下“1”，在I[1]中写下1。 tree = [0, 1, 0, 1], I=[3,1,0,0].
取3，在树[2]中写下“1”，在I[2]中写下0。 tree = [0, 1, 1, 1], I=[3,1,0,0].
取4，在树[0]中写下“1”，在I[3]中写下0。 tree = [1, 1, 1, 1], I=[3,1,0,0].

第二个技巧是使用高效的数据结构来计算在 O(n log n) 时间内看到的元素的数量，而不是像上面那样 O(n^2)。

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

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

Answer 2

同时，关于 pseudo-code，我找到了一个简单的解决方案，它也适用于 O(n log n)。

initialize AVL-tree T
initialize array I of length n
for i = 1, 2, ... , n:
    I[P[i]] = T.countGreaterThan(P[i])
    T.add(P[i])

将排列转换为反转表示

Converting permutation to inversion representation

algorithm

time-complexity

permutation

inversion