1.13. Инверсии

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

Пусть перестановка элементов множества Если пара называется инверсией перестановки. Например, перестановка 3142 имеет три инверсии Каждая инверсия — это пара элементов, «нарушающих порядок»; следовательно, единственная перестановка, не содержащая инверсий, — это отсортированная перестановка (

Таблицей инверсии перестановки называется последовательность где число элементов, больших и расположенных левее Другими словами, число инверсий, у которых второй элемент равен Например, таблица инверсий перестановки 591826473 будет 236402210, поскольку 5 и 9 расположены левее 1; 5, 9, 8 — левее 2 и т. д. Всего 20 инверсий. По определению

М. Холл установил, что таблица инверсий единственным образом определяет соответствующую перестановку. Из любой таблицы инверсий можно однозначно восстановить перестановку, которая порождает данную таблицу, путем последовательного определения относительного расположения элементов этом порядке). Например, перестановку, соответствующую таблице инверсий можно построить следующим образом: выпишем число 9; так как то 8 стоит правее 9. Поскольку то 7 стоит правее 8 и 9. Так как то 6 стоит правее двух уже выписанных чисел; таким образом, получили расположение 9,8,6,7. Припишем теперь 5 слева, потому что помещаем 4 вслед за четырьмя из уже записанных чисел, 3 — после шести выписанных чисел (т. е. в правый конец) и получаем 5,9,8,6,4,7,3. Вставив аналогичным образом 2 и 1, придем к перестановке (5,9,1,8,2,6,4,7,3).

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