Задача №2. Таблица инверсии

Задача:

Пусть P={p1,p2,…,pn} является перестановкой чисел 1,2,…,n. Таблицей инверсий перестановки P называют последовательность T={t1,t2,…,tn},в которой ti равно числу элементов перестановки P,стоящих в P левее i и больших i. Написать программу,которая по заданной таблице инверсий восстанавливает перестановку.


Решение

  1. О инверсиях
  2. Примеры инверсий
  3. Алгоритм
  4. Программирование
  5. Скриншоты
  6. Скачать
  7. Литература

О инверсиях

Пусть a1 a2 … an — перестановка множества {1,2,…,n}. Если i<j и ai > aj, то пара (ai,aj) называется инверсией перестановки; например, перестановка 3 1 4 2 имеет три инверсии: (3,1), (3,2) и (4,2). Каждая инверсия — это пара элементов, «нарушающих порядок»; следовательно, единственная перестановка, не содержащая инверсий, — это рассортированная перестановка 1 2 … n.

Понятие инверсии ввел Г. Крамер в 1750 году в связи со своим замечательным правилом решения линейных уравнений.

Таблица инверсии b1 b2 … b3 перестановки a1 a2 … an образуется, если определить bj как число элементов слева от j, которые больше, чем j. Другими словами, bj — число инверсий, второй элемент которых равен j. Отсюда, например, следует, что таблицей инверсии перестановки

5 9 1 8 2 6 4 7 3

будет

2 3 6 4 0 2 2 1 0

поскольку 5 и 9 расположены левее 1; 5,9,8 — левее 2 и т.д. Всего эта перестановка имеет 20 инверсий. По определению числа bj всегда удовлетворяют неравенствам

0 ≤ b1 ≤ n-1, 0 ≤ b2 ≤ n-2, …, 0 ≤ bn-1 ≤ 1, bn=0 (*)

Пожалуй, наиболее важный факт, касающийся перестановок и установленный Маршаллом Холлом(Marshall Hall), состоим в том, что таблица инверсий единственным образом определяет соответствующую перестановку. Из любой таблицы инверсии b1 b2 … bn, удовлетворяющей условиям (*), можно однозначно восстановить перестановку, которая ее породила, путем последовательного определения относительного расположения элементов n, n -1,…,1 (в этом порядке).

Примеры инверсий

Пример 1

Восстановить перестановку по таблице инверсий

таблица исходная [1,2,3,4,5,6,7,8]

таблица инверсии [7,3,0,2,1,0,1,0]

Решение

Перестановка содержит 8 номеров. Восстановление начинаем с числа 8. Ставим это число на неопределенное пока место

[       8         ]

В позиции 7 в таблице инверсий стоит число 1, следовательно, 7 стоит правее 8.

[       8 7       ]

В позиции 6 в таблице инверсий стоит 0, следовательно, 6 стоит левее всех уже поставленных чисел

[     6 8 7       ]

В позиции 5 в таблице инверсий стоит число 1, следовательно, 5 стоит правее 6.

[   6 5 8 7       ]

В позиции 4 в таблице инверсий стоит 2, следовательно, 4 стоит правее двух поставленных чисел, считая слева

[ 6 5 4 8 7       ]

В позиции 3 в таблице инверсий стоит 0, следовательно, 3 стоит левее всех уже поставленных чисел

[ 3 6 5 4 8 7     ]

В позиции 2 в таблице инверсий стоит 3, следовательно, 2 стоит правее трех поставленных чисел, считая слева

[ 3 6 5 2 4 8 7   ]

И, наконец, в первой позиции стоит 7. Ставим 1 на последнем месте, так, что перед 1 будет 7 чисел, больших 1.

Получаем искомую перестановку

[ 3 6 5 2 4 8 7 1 ]

Результат:

таблица исходная [1,2,3,4,5,6,7,8]

таблица инверсии [7,3,0,2,1,0,1,0]

Таблица перест.  [3,6,5,2,4,8,7,1]

Восстановление перестановки по таблице инверсий

Пример 2

Восстановить перестановку по таблице инверсий

таблица исходная [1,2,3,4,5,6,7,8,9]

таблица инверсии [5,0,1,3,8,4,2,6,8]

Решение

Перестановка содержит 9 номеров. Восстановление начинаем с числа 9. Ставим это число на неопределенное пока место

[       9           ]

В позиции 8 в таблице инверсий стоит число 6, следовательно, 8 стоит правее 9.

[       9 8         ]

В позиции 7 в таблице инверсий стоит 2, следовательно, 7 стоит правее на 2 числа всех уже поставленных чисел, считая слева.

[       9 8 7       ]

В позиции 6 в таблице инверсий стоит число 4, следовательно, 6 стоит правее на 4 числа всех уже поставленных чисел, считая слева.

[     9 8 7 6       ]

В позиции 5 в таблице инверсий стоит 8, следовательно, 5 стоит правее на 8 числа всех уже поставленных чисел, считая слева.

[   9 8 7 6 5       ]

В позиции 4 в таблице инверсий стоит 3, следовательно, 4 стоит правее на 3 числа всех уже поставленных чисел, считая слева.

[   9 8 7 4 6 5     ]

В позиции 3 в таблице инверсий стоит 1, следовательно, 3 стоит правее на 1 число всех уже поставленных чисел, считая слева.

[ 9 3 8 7 4 6 5     ]

В позиции 2 в таблице инверсий стоит 0, следовательно, 2 стоит поставить слева от поставленных чисел.

[ 2 9 3 8 7 4 6 5   ]

И, наконец, в первой позиции стоит 5, следовательно, 1 стоит правее на 5 чисел всех уже поставленных чисел, считая слева.

Получаем искомую перестановку

[ 2 9 3 8 7 1 4 6 5 ]

Результат:

таблица исходная [1,2,3,4,5,6,7,8,9]

таблица инверсии [5,0,1,3,8,4,2,6,8]

Таблица перест.  [2,9,3,8,7,1,4,6,5]

Алгоритм

Входной параметр таблица инверсии. Начинаем цикл от конца таблицы инверсии до начала, на каждом шаге проверяем 2 условия:

если в таблице инверсии текущий элемент равен 0, то в таблицу перестановок пишем номер элемента с самого начала;

если в таблице инверсии текущий элемент равен k и , то на k позиций смещаем относительно начала таблицы перестановок.

В конце получаем таблицу перестановок.

Программирование

В качестве структуры, которая будет хранить таблицу перестановок, используется строка (string).

функции, которые нам понадобятся:

  1. конкатенация (объединение строк)
  2. length() (длина строки)
  3. insert(pos,str) (вставить в позицию pos строку str)

По ходу цикла проверяем 3 условия:

если число в таблице инверсии = 0, то объединяем номер элемента в таблице инверсии с сторокой перестановок;

если число в таблице инверсии равно k и k меньше длины строки, то вставляем в строку перестановок в позицию k номер элемента;

если число в таблице инверсии равно k и k больше длины строки, то объединяем строку перестановок с номером элемента.

Скриншоты

Ссылки для скачивания

InvertTable.cpp

Литература

  1. Доналяд Э Кнут,Ю. В Козаченко,В. Т Тертышная,И. В Красиков «Искусство программирования: Сортировка и поиск», том 3.
Оцените статью
В коробке инженера
Добавить комментарий

Нажимая на кнопку "Добавить комментарий", я даю согласие на обработку персональных данных и принимаю политику конфиденциальности