Таблица инверсий — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Алгоритм построения)
Строка 1: Строка 1:
−
Пусть <tex> P = (p_1,p_2,\dots,p_n)</tex> является [[Действие перестановки на набор из элементов, представление в виде циклов|перестановкой]] чисел <tex> 1, 2,\dots, n</tex>.
+
<wikitex>
 +
Пусть $ P = (p_1,p_2,\dots,p_n)$ является [[Действие перестановки на набор из элементов, представление в виде циклов|перестановкой]] чисел $ 1, 2,\dots, n$.
  
 
{{Определение
 
{{Определение
 
|definition =  
 
|definition =  
−
'''Инверсией''' в перестановке <tex>P</tex> называется всякая пара индексов <tex>i, j</tex> такая, что <tex>1\leqslant i<j\leqslant n</tex> и <tex>P[i]>P[j]</tex>.
+
'''Инверсией''' в перестановке $P$ называется всякая пара индексов $i, j$ такая, что $1\leqslant i<j\leqslant n$ и $P[i]>P[j]$.
 
}}
 
}}
  
 
{{Определение
 
{{Определение
 
|definition =  
 
|definition =  
−
'''Таблицей инверсий''' перестановки <tex> P </tex> называют такую последовательность <tex> T = (t_1,t_2,\dots,t_n)</tex>, в которой <tex>t_i</tex> равно числу элементов перестановки <tex> P </tex>, стоящих в <tex> P </tex> левее числа <tex>i</tex> и больших <tex>i</tex>.
+
'''Таблицей инверсий''' перестановки $ P $ называют такую последовательность $ T = (t_1,t_2,\dots,t_n)$, в которой $t_i$ равно числу элементов перестановки $ P $, стоящих в $ P $ левее числа $i$ и больших $i$.
 
}}
 
}}
  
−
== Алгоритмы построения/восстановления ==  
+
=== Алгоритм построения ===
 +
 +
Таблицу инверсий тривиально построить по определению. Для каждого элемента перестановки считаем количество элементов, больших данного и стоящих в перестановке левее него.
 +
Алгоритм построения в псевдокоде выглядит так:
 +
$T[1..n] = 0$
 +
$For$ $i = 1..n$
 +
  $For$ $j = 1..(i - 1)$
 +
    $if$ $P[j] > P[i]$
 +
      $T[P[i]] = T[P[i]] + 1$
 +
Сложность данного алгоритма {{---}} $O(n^2)$. Уменьшить время работы можно используя [[Дерево отрезков. Построение|дерево отрезков]].
  
−
Ниже описанные алгоритмы работают за время О(n^2), но их можно ускорить до О(n*log(n)) ускорив процесс поиска, например двоичными деревьями.
+
Отсортируем элементы перестановки, сохраняя индексы. Массив $M$ будет содержать номер позиции каждого элемента в исходной перестановке. Также заведём массив $S$ длиной $n$, инициализированный нулями. После обработки $i$-го элемента будем вносить значение 1 в ячейку $S[M[i]]$. Обработку начинаем с последнего элемента и двигаемся к началу. Пусть, функция $Sum(i)$ возвращает значение суммы элементов массива $S$ от 1 до $i$ включительно. Тогда $i$-й элемент таблицы инверсий находится так:
−
 
+
$T[i] = Sum(M[i])$
−
 
+
Функция Sum реализуется с помощью [[Дерево отрезков. Построение|дерева отрезков]]. Каждое изменение массива и обращение к функции $Sum$ влечёт за собой $log_2 n$ операций. Таким образом получаем сложность алгоритма $O(n*log_2 n)$
−
=== Алгоритм построения ===
 
−
 
 
−
Для получения таблицы инверсий из таблицы перестановки вводим таблицу равной по длине таблице перестановки(не умаляя общности длина равна n) и на n-ное место записываем 0; ищем число i (от n-1 до 1) в таблице перестановки, и смотрим: сколько чисел больше i находится слева от числа i, полученное число записываем в таблицу инверсий на i-тое место.
 
  
 
=== Алгоритм восстановления ===  
 
=== Алгоритм восстановления ===  
Строка 53: Строка 60:
 
  [2 3 6 4 0 2 2 1 0] - т. инверсии
 
  [2 3 6 4 0 2 2 1 0] - т. инверсии
 
|-}
 
|-}
 +
</wikitex>

Версия 08:00, 14 ноября 2011

<wikitex> Пусть $ P = (p_1,p_2,\dots,p_n)$ является перестановкой чисел $ 1, 2,\dots, n$.


Определение:
Инверсией в перестановке $P$ называется всякая пара индексов $i, j$ такая, что $1\leqslant i<j\leqslant n$ и $P[i]>P[j]$.


Определение:
Таблицей инверсий перестановки $ P $ называют такую последовательность $ T = (t_1,t_2,\dots,t_n)$, в которой $t_i$ равно числу элементов перестановки $ P $, стоящих в $ P $ левее числа $i$ и больших $i$.


Алгоритм построения

Таблицу инверсий тривиально построить по определению. Для каждого элемента перестановки считаем количество элементов, больших данного и стоящих в перестановке левее него. Алгоритм построения в псевдокоде выглядит так: 

$T[1..n] = 0$ 
$For$ $i = 1..n$
  $For$ $j = 1..(i - 1)$
    $if$ $P[j] > P[i]$
      $T[P[i]] = T[P[i]] + 1$

Сложность данного алгоритма — $O(n^2)$. Уменьшить время работы можно используя дерево отрезков.

Отсортируем элементы перестановки, сохраняя индексы. Массив $M$ будет содержать номер позиции каждого элемента в исходной перестановке. Также заведём массив $S$ длиной $n$, инициализированный нулями. После обработки $i$-го элемента будем вносить значение 1 в ячейку $S[M[i]]$. Обработку начинаем с последнего элемента и двигаемся к началу. Пусть, функция $Sum(i)$ возвращает значение суммы элементов массива $S$ от 1 до $i$ включительно. Тогда $i$-й элемент таблицы инверсий находится так: 

$T[i] = Sum(M[i])$

Функция Sum реализуется с помощью дерева отрезков. Каждое изменение массива и обращение к функции $Sum$ влечёт за собой $log_2 n$ операций. Таким образом получаем сложность алгоритма $O(n*log_2 n)$

Алгоритм восстановления

Для восстановления таблицы перестановки из таблицы инверсий(не умаляя общности длина таблицы равна n) создаем таблицу, которую будем расширять, по мере добавления в неё чисел, добавляем в эту таблицу число i (где i от n до 1) на позицию k+1, где k - число в таблице инверсий на i-том месте.

Получение таблицы перестановки из таблицы инверсии 
[2 3 6 4 0 2 2 1 0] - т. инверсии
[9]
[9 8]
[9 8 7]
[9 8 6 7]
[5 9 8 6 7]
[5 9 8 6 4 7]
[5 9 8 6 4 7 3]
[5 9 8 2 6 4 7 3]
[5 9 1 8 2 6 4 7 3] - т. перестановки
</wikitex>
Получение таблицы инверсии из таблицы перестановки 
[5 9 1 8 2 6 4 7 3] - т. перестановки
[                0]
[              1 0]
[            2 1 0]
[          2 2 1 0]
[        0 2 2 1 0]
[      4 0 2 2 1 0]
[    6 4 0 2 2 1 0]
[  3 6 4 0 2 2 1 0]
[2 3 6 4 0 2 2 1 0] - т. инверсии
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Таблица_инверсий&oldid=13067»