Хорошо известно , что сортировка перестановок транспонирования в , так как минимальное число транспозиций требуется для сортировки л ∈ S п точно я п V ( л ) = { ( я , J ) ∈ [ п ] × [ N ] : i < j и π ( i ) > π ( j ) }, Это понятие «числа инверсии» находит применение и в алгебраической комбинаторике, например, оно позволяет наделить структурой решетки, называемой пермутоэдром и основанной на слабом порядке Брюа.
Это может быть полезным, чтобы переформулировать проблему в теоретико-групповых терминах. Нам дана группа с набором генераторов Γ и отображением i G : Γ ∗ → G , а также другая группа H, в которой G действует транзитивно, и мы хотим решить следующую задачу: для h ∈ H найти минимальную длину w ∈ Γ ∗ такой, что i G ( w ) . h = 1 ч . В случае перестановки G = H = и Γ - множество транспозиций.
Вопрос: есть ли другие примеры этой проблемы, которые допускают эффективные алгоритмы?
Ответы:
источник
источник