Инверсия графа на элемент

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) (я думаю), и мне было интересно, можно ли решить его более эффективно.

Я знаю Mergesort как, например, Показанный ниже часто используется для подсчета суммарных инверсий в 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})

Answer 2

На основании комментария @Andrew Scott, это изменение требуется:

import numpy as np
def mergeSortInversions(arr, counts):
  if len(arr) == 1:
    return arr, counts
  else:
    a = arr[:len(arr)//2]
    b = arr[len(arr)//2:]
    a, ai = mergeSortInversions(a, counts)
    b, bi = mergeSortInversions(b, counts)    
    c = []
    i = 0
    j = 0
    inversions = ai + bi

  while i < len(a) and j < len(b):
      if a[i] <= b[j]:
          c = np.concatenate([c, a[i, None]])
          i += 1
      else:
          c = np.concatenate([c, b[j, None]])
          inversions[a[i:].astype(np.int) - 1] += 1
          inversions[b[j].astype(np.int) - 1]  += (len(a)-i)
          j += 1

  c = np.concatenate([c, a[i:]])
  c = np.concatenate([c, b[j:]])
  return c, inversions

Answer 3

Вы можете изучить np.greater.outer (). Наружный метод уфунка.

import numpy as np
a = np.array([ 4, 2, 3, 1])

Создать квадратный массив с [i]> a [j] для всех i и j

arr = np.greater.outer(a,a)*1
arr
Out[24]:
array([[0, 1, 1, 1],
       [0, 0, 0, 1],
       [0, 1, 0, 1],
       [0, 0, 0, 0]])

Нас интересует только верхний правый треугольник.

arr = np.triu(arr)
arr
Out[25]:
array([[0, 1, 1, 1],
       [0, 0, 0, 1],
       [0, 0, 0, 1],
       [0, 0, 0, 0]])

arr += arr.T # add the transposition.  arr is symmetrical about the diagonal.
arr  
Out[9]:
array([[0, 1, 1, 1],
       [1, 0, 0, 1],
       [1, 0, 0, 1],
       [1, 1, 1, 0]])

Суммируйте строки, чтобы получить количество.

arr.sum(axis = 0)
Out[28]: array([3, 2, 2, 3])

Все циклы скрыты во внешнем методе.