Преобразования перестановки инверсия представления

Question

P = [a1, a2, ... , aN] Перестановка из первых N натуральных чисел могут быть представлены в виде списка inversionsI = [i1, i2, ... , iN], где iK говорит нам, сколько чисел, которые больше, чем K можно найти до K в перестановке P.

Пример: если P = [3, 1, 4, 2], то I = [1, 2, 0, 0] (3 помещается 1, 3 и 4 помещается до 2, тогда как 3 и 4 не предшествует большему числу).

Существует очевидный алгоритм, который преобразует перестановку из стандартной в форму инверсии и запускается в O(N^2) (мы просто следуем определению и подсчету). То же самое справедливо и для обратного преобразования (что несколько менее прямолинейно).

Есть ли алгоритм, который имеет более низкую временную сложность?

Answer 1

Существует простой итеративный алгоритм динамического программирования для решения этой проблемы: для всех я от 1 до n (длина перестановки) взять номер i и посмотреть, сколько элементов в P слева от i уже видели , Поскольку мы обрабатываем i в порядке возрастания, мы знаем, что элементы not видны элементами, большими, чем i - и поэтому мы подсчитываем и записываем количество этих элементов. Хитрость заключается в том, чтобы ввести внешний список, чем отслеживать, какие элементы в P уже были замечены.

Для начала давайте посмотрим, как это сделать в способе O(n^2). Например, если P=[4, 3, 2, 1], то алгоритм будет выполняться следующим образом:

1. Создать структуру tree инициализируется нулями. Он содержит «1» в позиции j, если элемент с j-й позицией в P уже был замечен итерационным алгоритмом.

2. Принять 1, определить, что pos==3. Напишите «1» вниз в tree[pos]. Вычислите num_seen=sum(tree[0:3]), который равен 0. Запишите pos - num_seen + 1 на I[0]. После этого: tree = [0, 0, 0, 1], I = [3, 0, 0, 0]

3. Возьмите 2, напишите «1» вниз в дереве [1] и 1 в I [1]. .

4. Возьмите 3, напишите «1» вниз в дереве [2] и 0 в I [2]. tree = [0, 1, 1, 1], I=[3,1,0,0].

5. Возьмите 4, напишите «1» вниз в дереве [0] и 0 в I [3]. tree = [1, 1, 1, 1], I=[3,1,0,0].

Второй фокус в том, чтобы использовать эффективную структуру данных, чтобы подсчитать количество видимых элементов в O(n log n) времени вместо O(n^2), как описано выше.

Вот 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 

Answer 2

Между тем, я нашел простое решение, о псевдо-код, который работает в 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])