Можем ли мы отсортировать без перестановок?

12

Хорошо известно , что сортировка перестановок транспонирования в , так как минимальное число транспозиций требуется для сортировки л S п точно я п V ( л ) = { ( я , J ) [ п ] × [ N ] : i < j  и  π ( i ) > π ( j ) }PπSninv(π)={(i,j)[n]×[n]:i<j and π(i)>π(j)}, Это понятие «числа инверсии» находит применение и в алгебраической комбинаторике, например, оно позволяет наделить структурой решетки, называемой пермутоэдром и основанной на слабом порядке Брюа.Sn

Это может быть полезным, чтобы переформулировать проблему в теоретико-групповых терминах. Нам дана группа с набором генераторов Γ и отображением i G : Γ G , а также другая группа H, в которой G действует транзитивно, и мы хотим решить следующую задачу: для h H найти минимальную длину w Γ такой, что i G ( w ) . h = 1 ч . В случае перестановки G = H =GΓiG:ΓGHGhHwΓiG(w).h=1H и Γ - множество транспозиций.G=H=SnΓ

Вопрос: есть ли другие примеры этой проблемы, которые допускают эффективные алгоритмы?

NisaiVloot
источник
Ну, проблема, вероятно, проста, когда G=iZri
пельмени Мобиуса

Ответы:

6

XH(x1,,xn)Xnx1xn=1XGBnσiBnH

σi(x1,,xn)=(x1,,xi1,xi+1,xi+11xixi+1,,xn).

σiii+1

NisaiVloot
источник
4

G=H=SnG=H=An

  • Марк Джеррум: сложность поиска последовательностей генератора минимальной длины. Теор. Вычи. Sci. 36: 265-289 (1985) http://dx.doi.org/10.1016/0304-3975(85)90047-7 .

G=H=SnΓw

Ёсио Окамото
источник