python - 计数每个元素的反转

Question

我想计算某些列表的每个元素 的反转次数。如果i < j和 list[i] > list[j]然后是一对(i, j)是一个反转。许多算法计算这些对的总数，而我想计算一些列表的所有元素，这些元素作为反转对的一部分的频率。

考虑例如此列表:[4, 2, 3, 1]

有五个反转对:(4, 2), (4, 3), (4, 1), (2, 1), (3, 1) .我知道您可以通过嵌套的 for 循环(或使用矢量化)获取元素计数，例如:

import numpy as np
lst = np.array([4,2,3,1])
inv_count = np.zeros(lst.size)

for i in np.arange(lst.size - 1):
  idx = np.where(lst[i] > lst[(i+1):])[0] + i + 1
  inv_count[idx] += 1
  inv_count[i] += idx.size

产生正确的结果

array([3., 2., 2., 3.])

但那是在 O(n^2) 中运行的(我认为)我想知道是否可以更有效地解决它。

我知道合并排序，例如下面显示的经常用于计算 O(n log n) 中的总反转，但我不确定如何采用它来计算每个元素？

def mergeSortInversions(arr):
  if len(arr) == 1:
    return arr, 0
  else:
    a = arr[:len(arr)//2]
    b = arr[len(arr)//2:]
    a, ai = mergeSortInversions(a)
    b, bi = mergeSortInversions(b)
    c = []
    i = 0
    j = 0
    inversions = 0 + ai + bi
  while i < len(a) and j < len(b):
    if a[i] <= b[j]:
      c.append(a[i])
      i += 1
    else:
      c.append(b[j])
      j += 1
      inversions += (len(a)-i)
  c += a[i:]
  c += b[j:]
  return c, inversions

Answer 1

您可以使用函数 combinations() 和 filter() 来构建带反转的列表:

from itertools import combinations

l = [4, 2, 3, 1]

list(filter(lambda x: x[0] > x[1], combinations(l, 2)))
# [(4, 2), (4, 3), (4, 1), (2, 1), (3, 1)]

您可以使用 defaultdict() 来计算反转:

from itertools import combinations
from collections import defaultdict

l = [4, 2, 3, 1]

dd = defaultdict(int)

for i, j in combinations(l, 2):
    if i > j:
        dd[i] += 1
        dd[j] += 1

print(dd)
# defaultdict(<type 'int'>, {1: 3, 2: 2, 3: 2, 4: 3})