Инверсия (дискретная математика)

Перестановка с выделенной одной из инверсий.. Может быть обозначена парой знаков (2, 4) или пару элементов (5, 2).

В информатике и дискретной математике последовательность имеет инверсию, где два из его элементы находятся вне их естественного порядка.

Содержание

• 1 Определения
  • 1.1 Инверсия
  • 1.2 Номер инверсии
  • 1.3 Инверсия связанных векторов
• 2 Пример: все перестановки четырех элементов
• 3 Слабый порядок перестановок
• 4 См. Также
• 5 Ссылки
  • 5.1 Библиография источников
  • 5.2 Дополнительная литература
  • 5.3 Меры предварительной сортировки

Определения

Инверсия

Пусть $\pi \; \{\backslash \; displaystyle\; \backslash \; pi\}$будет перестановкой. Если и $\pi \; (i)>\pi \; (j)\; \{\backslash \; displaystyle\; \backslash \; pi\; (i)>\backslash \; pi\; (j)\}$, либо пара мест $(i,\; j)\; \{\; \backslash \; displaystyle\; (i,\; j)\}$или пара элементов $(\pi \; (i),\; \pi \; (j))\; \{\backslash \; displaystyle\; \{\backslash \; bigl\; (\}\; \backslash \; pi\; (i),\; \backslash \; pi\; (\; j)\; \{\backslash \; bigr)\}\}$называется инверсией из $\pi \; \{\backslash \; displaystyle\; \backslash \; pi\}$.

Инверсия обычно определяется для перестановок, но также может быть определено для последовательностей:. Пусть $S\; \{\backslash \; displaystyle\; S\}$будет последовательностью (или мультимножеством перестановкой). Если и $S\; (я)>S\; (j)\; \{\backslash \; displaystyle\; S\; (i)>S\; (j)\}$, либо пара мест $(i,\; j)\; \{\backslash \; displaystyle\; (i,\; j)\}$или пара элементов $(S\; (я),\; S\; (j))\; \{\backslash \; displaystyle\; \{\backslash \; bigl\; (\}\; S\; (i),\; S\; (j)\; \{\backslash \; bigr)\}\}$называется инверсией $S\; \{\backslash \; displaystyle\; S\}$.

Для последовательностей инверсии согласно определению на основе элементов не уникальны, потому что разные пары позиций могут иметь одну и ту же пару значений.

Набор инверсии - это набор всех инверсий. Набор инверсии перестановки в соответствии с определением на основе места - это набор инверсии перестановки обратной перестановки в соответствии с определением на основе элементов, и наоборот, только при обмене элементами пар.

Номер инверсии

Номер инверсии - это мощность набора инверсии. Это обычная мера сортировки перестановки или последовательности.

Это количество пересечений на стрелочной диаграмме перестановки, ее расстояние Кендалла от идентичной перестановки и сумма каждого из векторов, связанных с инверсией, определенных ниже.

Не имеет значения, используется ли определение инверсии по месту или по элементам для определения числа инверсии, потому что перестановка и ее инверсия имеют одинаковое количество инверсий.

Другие меры (предварительной) сортировки включают минимальное количество элементов, которые могут быть удалены из последовательности, чтобы получить полностью отсортированную последовательность, количество и длину отсортированных «прогонов» в последовательности, правило Спирмена. (сумма расстояний каждого элемента от его отсортированной позиции) и наименьшее количество обменов, необходимых для сортировки последовательности. Стандартные алгоритмы сортировки сравнения могут быть адаптированы для вычисления числа инверсии за время O (n log n).

Векторы, связанные с инверсией

Используются три похожих вектора, которые уплотняют инверсия перестановки в вектор, который однозначно ее определяет. Их часто называют вектором инверсии или кодом Лемера. (Список источников находится здесь.)

В этой статье используется термин вектор инверсии ($v\; \{\backslash \; displaystyle\; v\}$), например Вольфрам. Оставшиеся два вектора иногда называют левым и правым векторами инверсии, но во избежание путаницы с вектором инверсии в этой статье они называются счетчиком левой инверсии ($l\; \{\backslash \; displaystyle\; l\}$) и счетчиком правой инверсии ( $р\; \{\backslash \; displaystyle\; r\}$). Интерпретируемое как факториальное число, количество левой инверсии дает перестановки, обратные колексикографическим, а количество правой инверсии дает лексикографический индекс.

Диаграмма Роте

Вектор инверсии $v\; \{\backslash \; displaystyle\; v\}$:. с определением на основе элементов $v\; (i)\; \{\backslash \; displaystyle\; v\; (i)\}$is количество инверсий, меньший (правый) компонент которого равен $i\; \{\backslash \; displaystyle\; i\}$.

$v\; (i)\; \{\backslash \; displaystyle\; v\; (i)\}$- количество элементов в $\pi \; \{\backslash \; displaystyle\; \backslash \; pi\}$больше, чем $i\; \{\backslash \; displaystyle\; i\}$до $i\; \{\backslash \; displaystyle\; i\}$.

Количество инверсий влево $l\; \{\backslash \; displaystyle\; l\}$:. С определением на основе места $l\; (i)\; \{\backslash \; displaystyle\; l\; (i)\}$- количество инверсий, у которых больше (справа) компонент - это $i\; \{\backslash \; displaystyle\; i\}$.

$l\; (i)\; \{\backslash \; displaystyle\; l\; (i)\}$- количество элементов в $\pi \; \{\backslash \; displaystyle\; \backslash \; pi\; \}$больше, чем $\pi \; (i)\; \{\backslash \; displaystyle\; \backslash \; pi\; (i)\}$до $\pi \; (i)\; \{\backslash \; displaystyle\; \backslash \; pi\; (i)\}$.

Количество правых инверсий $\{\backslash \; displaystyle\; r\}$, часто называемый кодом Лемера :. с определением на основе места $r\; (i)\; \{\backslash \; displaystyle\; r\; (i)\}$is количество инверсий, меньший (левый) компонент которых равен $i\; \{\backslash \; displaystyle\; i\}$.

$r\; (i)\; \{\backslash \; displaystyle\; r\; (i)\}$- это количество элементов в $\pi \; \{\backslash \; displaystyle\; \backslash \; pi\}$меньше, чем $\pi \; (i)\; \{\backslash \; displaystyle\; \backslash \; pi\; (i)\}$после $\pi \; (i)\; \{\backslash \; displaystyle\; \backslash \; pi\; (i)\}$.

И $v\; \{\backslash \; displaystyle\; v\}$, и $r\; \{\backslash \; displaystyle\; r\}$можно найти с помощью Rothe диаграмма, которая представляет собой матрицу перестановок с единицами, представленными точками, и inv в каждой позиции, где справа и снизу есть точка. $r\; (i)\; \{\backslash \; displaystyle\; r\; (i)\}$- сумма инверсий в строке $i\; \{\backslash \; displaystyle\; i\}$диаграммы Роте, а $v\; (i)\; \{\backslash \; displaystyle\; v\; (i)\}$- сумма инверсий в столбце $i\; \{\backslash \; displaystyle\; i\}$. Матрица перестановок обратного преобразования - это транспонирование, поэтому $v\; \{\backslash \; displaystyle\; v\}$перестановки равно $r\; \{\backslash \; displaystyle\; r\}$его обратного, и наоборот.

Пример: все перестановки четырех элементов

Шесть возможных инверсий 4-элементной перестановки

В следующей сортируемой таблице показаны 24 перестановки четырех элементов с их наборами инверсии на основе места, связанными с инверсией векторы и числа инверсии. (Маленькие столбцы являются отражением соседних столбцов, и их можно использовать для сортировки в колексикографическом порядке.)

Можно видеть, что $v\; \{\backslash \; displaystyle\; v\; \}$и $l\; \{\backslash \; displaystyle\; l\}$всегда имеют одинаковые цифры, а $l\; \{\backslash \; displaystyle\; l\}$и $r\; \{\backslash \; displaystyle\; r\}$оба связаны с набором инверсии на основе места. Нетривиальные элементы $l\; \{\backslash \; displaystyle\; l\}$представляют собой суммы убывающих диагоналей показанного треугольника, а элементы $r\; \{\backslash \; displaystyle\; r\}$равны суммы диагоналей по возрастанию. (Пары в нисходящих диагоналях имеют общие правые компоненты 2, 3, 4, а пары в восходящих диагоналях имеют общие левые компоненты 1, 2, 3.)

Порядок таблицы по умолчанию - обратный колекс упорядочить по $\pi \; \{\backslash \; displaystyle\; \backslash \; pi\}$, что совпадает с порядком colex по $l\; \{\backslash \; displaystyle\; l\}$. Порядок Lex на $\pi \; \{\backslash \; displaystyle\; \backslash \; pi\}$совпадает с порядком lex на $r\; \{\backslash \; displaystyle\; r\}$.

3-элементные перестановки для сравнения

0 1 2 3 4 5 $\pi \; \{\backslash \; displaystyle\; \backslash \; pi\}$ $v\; \{\backslash \; displaystyle\; v\}$ $l\; \{\backslash \; displaystyle\; l\}$ pb $r\; \{\backslash \; displaystyle\; r\}$ # 0 123 321 000 000 000 000 000 000 0 1 213 312 100 001 010 010 100 001 1 2 132 231 010 010 100 001 010 010 1 3 312 213 110 011 110 011 200 002 2 4 231 132 200 002 200 002 110 011 2 5 321 123 210 012 210 012 210 012 3

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

$\pi \; \{\backslash \; displaystyle\; \backslash \; pi\; \}$ $v\; \{\backslash \; displaystyle\; v\}$ $l\; \{\backslash \; dis\; playstyle\; l\}$ pb $r\; \{\backslash \; displaystyle\; r\}$ # 0 1234 4321 0000 0000 0000 0000 0000 0000 0 1 2134 4312 1000 0001 0010 0100 1000 0001 1 2 1324 4231 0100 0010 0100 0010 0100 0010 1 3 3124 4213 1100 0011 0110 0110 2000 0002 2 4 2314 4132 2000 0002 0200 0020 1100 0011 2 5 3214 4123 2100 0012 0210 0120 2100 0012 3 6 1243 3421 0010 0100 1000 0001 0010 0100 1 7 2143 3412 1010 0101 1010 0101 1010 0101 2 8 1423 3241 0110 0110 1100 0011 0200 0020 2 9 4123 3214 11 10 0111 1110 0111 3000 0003 3 10 2413 3142 2010 0102 1200 0021 1200 0021 3 11 4213 3124 2110 0112 1210 0121 3100 0013 4 12 1342 2431 0200 0020 2000 0002 0110 0110 2 13 3142 2413 1200 0021 2010 0102 2010 0102 3 14 1432 2341 0210 0120 2100 0012 0210 0120 3 15 4132 2314 1210 0121 2110 0112 3010 0103 4 16 3412 2143 2200 0022 2200 0022 2200 0022 4 17 4312 2134 2210 0122 2210 0122 3200 0023 5 18 2341 1432 3000 0003 3000 0003 1110 0111 3 19 3241 1423 3100 0013 3010 0103 2110 0112 4 20 2431 1342 3010 0103 3100 0013 1210 0121 4 21 4231 1324 3110 0113 3110 0113 3110 0113 5 22 3421 1243 3200 0023 3200 0023 2210 0122 5 23 4321 1234 3210 0123 3210 0123 3210 0123 6

Слабый порядок перестановок

Перммутоэдр симметричной группы S4

Множеству перестановок на n элементах может быть задана структура частичного порядка, называемого слабым порядком перестановок, который образует решетку.

Диаграмма Хассе наборов инверсии, упорядоченных отношением подмножество, образует каркас пермутоэдра.

Если перестановка назначена к каждому набору инверсии с использованием определения на основе места, результирующий порядок перестановки Это пермутоэдр, где ребро соответствует перестановке двух элементов с последовательными значениями. Это слабый порядок перестановок. Идентичность - это его минимум, а перестановка, образованная обращением идентичности, - это его максимум.

Если бы перестановка была назначена каждому набору инверсии с использованием определения на основе элементов, результирующий порядок перестановок был бы таким же, как у графа Кэли, где ребро соответствует замене двух элементы на последовательных местах. Этот граф Кэли симметрической группы похож на свой пермутоэдр, но с каждой перестановкой, замененной своей обратной.

См. Также

В Викиверситете есть учебные ресурсы по инверсии (дискретная математика)

На Викискладе есть материалы, связанные с инверсией (дискретная математика).

• Факториальная система счисления
• Граф перестановок
• Транспозиции, простые транспозиции, инверсии и сортировка
• Расстояние Дамерау – Левенштейна
• Четность перестановки

Последовательности в OEIS :

• Последовательности, связанные с факториалом базовое представление
• Факториальные числа: A007623 и A108731
• Номера инверсии: A034968
• Инверсионные наборы конечных перестановок, интерпретируемых как двоичные числа: A211362 (связанная перестановка: A211363 )
• Конечные перестановки, которые имеют только нули и единицы в своих векторах инверсии: A059590 (их наборы инверсии: A211364 )
• Количество перестановок n элементов с k инверсий; числа Махона: A008302 (их максимумы строк; числа Кендалла-Манна: A000140 )
• Число связанных помеченных графов с n ребер и n узлов: A057500

Ссылки

Библиография источников

Дополнительная литература

Меры предварительной сортировки