В информатике и дискретной математике , инверсия в последовательности пара элементов , которые находятся вне их естественного порядка .
Определения
Инверсия
Позволять быть перестановкой . Если а также , либо пара мест [1] [2] или пара элементов[3] [4] [5] называется инверсией из.
Инверсия обычно определяется для перестановок, но также может быть определена для последовательностей:
Пустьбыть последовательность (или мультимножество перестановки [6] ). Если а также , либо пара мест [6] [7] или пара элементов[8] называется обращением.
Для последовательностей инверсии согласно определению на основе элементов не уникальны, потому что разные пары мест могут иметь одну и ту же пару значений.
Множество инверсии является множеством всех инверсий. Набор инверсии перестановки в соответствии с определением на основе места - это набор инверсии обратной перестановки в соответствии с определением на основе элементов, и наоборот, [9] только с замененными элементами пар.
Номер инверсии
Число инверсии [10] последовательности, - мощность множества инверсии. Это обычные меры (предварительной) сортировки перестановки [5] или последовательности. [8] Это значение находится в диапазоне от 0 до включены.
Например так как последовательность упорядочена. Также как каждая пара это инверсия. Этот последний пример показывает, что интуитивно отсортированная сортировка может иметь квадратичное количество инверсий.
Это количество пересечений на стрелочной диаграмме перестановки [9], его тау-расстояние Кендалла от тождественной перестановки и сумма каждого из векторов, связанных с инверсией, определенных ниже.
Не имеет значения, используется ли определение инверсии по месту или по элементам для определения числа инверсии, потому что перестановка и ее инверсия имеют одинаковое количество инверсий.
Другие меры (предварительной) сортировки включают минимальное количество элементов, которые можно удалить из последовательности, чтобы получить полностью отсортированную последовательность, количество и длину отсортированных «прогонов» в последовательности, правило Спирмена (сумма расстояний каждого элемент из его отсортированной позиции) и наименьшее количество обменов, необходимых для сортировки последовательности. [11] Стандартные алгоритмы сортировки сравнения могут быть адаптированы для вычисления числа инверсии за время O ( n log n ) . [12]
Используются три похожих вектора, которые конденсируют инверсии перестановки в вектор, который однозначно определяет ее. Их часто называют вектором инверсии или кодом Лемера . (Список источников можно найти здесь .)
В этой статье используется термин вектор инверсии () как Вольфрам . [13] Оставшиеся два вектора иногда называются левым и правым векторами инверсии , но, чтобы избежать путаницы с вектором инверсии, в этой статье они называются счетчиком левой инверсии () и счетчик правых инверсий (). Интерпретируемое как факториальное число, количество левой инверсии дает перестановки, обратные колексикографическим, [14], а количество правой инверсии дает лексикографический индекс.
Вектор инверсии :
С определением на основе элементов- количество инверсий, меньшая (правая) компонента которых равна. [3]
- количество элементов в больше чем перед .
Счетчик левой инверсии :
С определением на основе места- количество инверсий, большая (правая) составляющая которых равна.
- количество элементов в больше чем перед .
Правый счет инверсии , часто называемый кодом Лемера :
с определением на основе места- количество инверсий, меньшая (левая) компонента которых равна.
- количество элементов в меньше чем после .
Оба а также можно найти с помощью диаграммы Роте , которая представляет собой матрицу перестановок с единицами, представленными точками, и инверсией (часто представленной крестиком) в каждой позиции, которая имеет точку справа и ниже. это сумма инверсий в строке диаграммы Роте, а это сумма инверсий в столбце . Матрица перестановки обратного является транспонированной, поэтому перестановки его обратного, и наоборот.
Пример: все перестановки четырех элементов
В следующей сортируемой таблице показаны 24 перестановки четырех элементов с их наборами инверсии на основе места, векторами, связанными с инверсией, и числами инверсии. (Маленькие столбцы являются отражением соседних столбцов, и их можно использовать для сортировки в колексикографическом порядке .)
Видно, что а также всегда иметь одинаковые цифры, и это а также оба связаны с набором инверсии по месту. Нетривиальные элементы - суммы убывающих диагоналей показанного треугольника, а диагонали - суммы возрастающих диагоналей. (Пары в нисходящих диагоналях имеют общие правые компоненты 2, 3, 4, а пары в восходящих диагоналях имеют общие левые компоненты 1, 2, 3.)
Порядок таблицы по умолчанию - обратный порядок колекса по , что совпадает с порядком колекса по . Лекс заказывается то же самое, что и lex order by .
3-элементные перестановки для сравнения | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
|
|
Слабый порядок перестановок
Множеству перестановок на n элементах можно придать структуру частичного порядка , называемого слабым порядком перестановок , который образует решетку .
Хасса схема множеств инверсии упорядоченных по подмножеству отношению образует скелет из более перестановочного многогранника .
Если перестановка назначается каждому набору инверсии с использованием определения на основе места, результирующий порядок перестановок соответствует порядку перестановок, где ребро соответствует перестановке двух элементов с последовательными значениями. Это слабый порядок перестановок. Идентичность - это ее минимум, а перестановка, образованная путем изменения идентичности, - ее максимум.
Если бы перестановка была назначена каждому набору инверсии с использованием определения на основе элементов, результирующий порядок перестановок был бы порядком перестановок графа Кэли , где ребро соответствует перестановке двух элементов в последовательных местах. Этот граф Кэли симметрической группы подобен своему пермутоэдру, но с каждой перестановкой, замененной своей обратной.
Смотрите также
- Факторная система счисления
- Граф перестановок
- Транспозиции, простые транспозиции, инверсии и сортировка
- Расстояние Дамерау – Левенштейна
- Четность перестановки
Последовательности в OEIS :
- Последовательности, относящиеся к факторному базовому представлению
- Факторные номера: A007623 и A108731
- Номера версий : A034968
- Наборы инверсий конечных перестановок, интерпретируемых как двоичные числа: A211362 (связанная перестановка: A211363 )
- Конечные перестановки, в векторах инверсии которых есть только нули и единицы: A059590 (их наборы инверсии: A211364 )
- Количество перестановок n элементов с k инверсиями; Числа Махониана: A008302 (их максимумы ряда; числа Кендалла-Манна: A000140 )
- Количество связанных помеченных графов с n ребрами и n узлами: A057500
Рекомендации
- Перейти ↑ Aigner 2007 , pp. 27.
- ^ Комте 1974 , стр. 237.
- ^ a b Knuth 1973 , стр. 11.
- ^ Пеммараджу & Skiena 2003 , стр. 69.
- ^ Б Vitter & Flajolet 1990 , стр. 459.
- ^ Б Bona 2012 , стр. 57.
- ^ Кормен и др. 2001 , с. 39.
- ^ a b Barth & Mutzel 2004 , стр. 183.
- ↑ a b Gratzer 2016 , pp. 221.
- ^ Mannila, 1984 и pp318 .
- ↑ Махмуд, 2000 , с. 284.
- ^ Клейнберг & Tardos 2005 , стр. 225.
- ^ Вайсштейн, Эрик В. "Вектор инверсии" из MathWorld - Интернет-ресурс Wolfram
- ^ Обратный колексный порядок конечных перестановок (последовательность A055089 в OEIS )
Библиография источников
- Айгнер, Мартин (2007). «Представление слова». Курс по перечислению . Берлин, Нью-Йорк: Springer. ISBN 978-3642072536.
- Барт, Вильгельм; Муцель, Петра (2004). «Простой и эффективный двухслойный кросс-счет» . Журнал графических алгоритмов и приложений . 8 (2): 179–194. DOI : 10,7155 / jgaa.00088 .
- Бона, Миклош (2012). «2.2 Инверсии в перестановках мультимножеств». Комбинаторика перестановок . Бока-Ратон, Флорида: CRC Press. ISBN 978-1439850510.
- Контет, Луи (1974). «6.4 Обращения перестановки [n]». Продвинутая комбинаторика; искусство конечных и бесконечных расширений . Дордрехт, Бостон: D. Reidel Pub. Co. ISBN 9027704414.
- Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Стейн, Клиффорд (2001). Введение в алгоритмы (2-е изд.). MIT Press и McGraw-Hill. ISBN 0-262-53196-8. CS1 maint: обескураженный параметр ( ссылка )
- Гратцер, Джордж (2016). «7-2 Основные объекты». Теория решеток. специальные темы и приложения . Чам, Швейцария: Birkhäuser. ISBN 978-3319442358. CS1 maint: обескураженный параметр ( ссылка )
- Клейнберг, Джон; Тардос, Ива (2005). Разработка алгоритмов . ISBN 0-321-29535-8.
- Кнут, Дональд (1973). «5.1.1 Инверсии». Искусство программирования . Аддисон-Уэсли Паб. Co. ISBN 0201896850.
- Махмуд, Хосам Махмуд (2000). «Сортировка неслучайных данных». Сортировка: теория распределения . Серия Wiley-Interscience по дискретной математике и оптимизации. 54 . Wiley-IEEE. ISBN 978-0-471-32710-3.
- Pemmaraju, Sriram V .; Скиена, Стивен С. (2003). «Перестановки и комбинации». Вычислительная дискретная математика: комбинаторика и теория графов в системе Mathematica . Издательство Кембриджского университета. ISBN 978-0-521-80686-2.
- Виттер, JS; Флажолет, доктор наук (1990). «Средний случай анализа алгоритмов и структур данных». В ван Леувен, Ян (ред.). Алгоритмы и сложность . 1 (2-е изд.). Эльзевир. ISBN 978-0-444-88071-0.
дальнейшее чтение
- Марголиус, Барбара Х. (2001). «Перестановки с инверсиями». Журнал целочисленных последовательностей . 4 .
Меры пресортированности
- Маннила, Хейкки (1984). «Меры пресортированности и оптимальные алгоритмы сортировки». Конспект лекций по информатике . 172 : 324–336. DOI : 10.1007 / 3-540-13345-3_29 . ISBN 978-3-540-13345-2. CS1 maint: обескураженный параметр ( ссылка )
- Эстивиль-Кастро, Владимир; Вуд, Дерик (1989). «Новая мера пресортированности» . Информация и вычисления . 83 (1): 111–119. DOI : 10.1016 / 0890-5401 (89) 90050-3 .
- Скиена, Стивен С. (1988). «Посягающие списки как мера предварительной сортировки». БИТ . 28 (4): 755–784. DOI : 10.1007 / bf01954897 . S2CID 33967672 .