Восстановление перестановки по таблице инверсий
Пример. Восстановить перестановку по таблице инверсий
Решение.
Перестановка содержит 8 номеров. Восстановление начинаем с числа 8. Ставим это число на неопределенное пока место
В позиции 7 в таблице инверсий стоит число 1, следовательно, 7 стоит правее 8.
В позиции 6 в таблице инверсий стоит 0, следовательно, 6 стоит левее всех уже поставленных чисел
В позиции 5 в таблице инверсий стоит число 1, следовательно, 5 стоит правее 6.
В позиции 4 в таблице инверсий стоит 2, следовательно, 4 стоит правее двух поставленных чисел, считая слева
В позиции 3 в таблице инверсий стоит 0, следовательно, 3 стоит левее всех уже поставленных чисел
В позиции 2 в таблице инверсий стоит 3, следовательно, 2 стоит правее трех поставленных чисел, считая слева
И, наконец, в первой позиции стоит 7. Ставим 1 на последнем месте, так, что перед 1 будет 7 чисел, больших 1. Получаем
искомую перестановку
|