Заведем массив А из 0 и 1, в котором А[i] равно 0, если мы еще не поставили число i в перестановку, и 1 - иначе. Обрабатываем таблицу инверсий справа налево. На каждом шаге i мы на i-тое место в будущей перестановке ставим индекс φ[i]+1 нуля в массиве А, считая справа налево, после этого изменяем ноль на единицу.