Задача:

— нужно использовать в программе перестановки. При этом должно быть возможно получить значение перестановки, а также значение обратной перестановки на некотором элементе за время O(1). Перестановки составляются из транспозиций (перестановок пары элементов). То есть, сначала есть тождественная перестановка, затем мы домножаем её на транспозиции справа. Операция домножения на транспозицию справа тоже должна быть реализована за время O(1).

Эквивалентная задача:

— нужно уметь домножать перестановку справа на транспозицию за время O(1), и в то же время уметь домножать её слева на транспозицию за O(1).