21
правка
Изменения
Алгоритмы
Пусть <tex> P = (p_1,p_2,\dots,p_n)</tex> является [[Действие перестановки на набор из элементов, представление в виде циклов|перестановкой]] чисел <tex> 1, 2,\dots, n</tex>.
{{Определение
|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>.
}}
{| width="150" align="right" cellpadding="5" border="1" style="border-collapse: collapse;"
|-
| <span style="font-size:smaller;">Получение таблицы инверсии из таблицы перестановки</span>
[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] - т. инверсии
|-
| <span style="font-size:smaller;">Получение таблицы перестановки из таблицы инверсии</span>
[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] - т. перестановки
|-}
== Алгоритм построения ==
Для получения таблицы инверсий из таблицы перестановки вводим таблицу равной по длине таблице перестановки(не умаляя общности длина равна n) и на n-ное место записываем 0; ищем число i(от n-1 до 1) в таблице перестановки, и смотрим: сколько чисел больше i находится слева от числа i, полученное число записываем в таблицу инверсий на i-тое место.
== Алгоритм восстановления ==
Для восстановления таблицы перестановки из таблицы инверсий(не умаляя общности длина таблицы равна n) создаем таблицу, которую будем расширять, по мере добавления в неё чисел, добавляем в эту таблицу число i(где i от n до 1) на позицию k+1, где k - число в таблице инверсий на i-том месте.
