Изменения

'''Умножением''' (англ. ''multiplication'') или '''композицией''' (англ. ''composition'') перестановок,представленных в виде целочисленных функций <tex> a_i </tex>, где <tex>i - </tex> позиция элемента, а <tex> a_i </tex> — его номер, называется перестановка, получаемая по следующему правилу:

<tex> (ab)_i = a_b_{b_ia_i} </tex>

# <tex> (a(bc))_i = a_{(bc)_i_{a_i} = a_c_{b_{c_ia_i}} </tex># <tex> ((ab)c)_i = c_{(ab)_{c_i_i} = a_c_{b_{c_ia_i}} </tex>

'''Обратной перестановкой''' (англ. ''an inverse permutation'') <tex> a^{-1} </tex> к перестановке <tex> a </tex> называется такая перестановка, что:

Для каждой перестановки существует перестановка, обратная ей.

Пусть в массиве <tex>p[i]</tex> содержится перестановка, длины <tex> n </tex>, тогда после выполнения алгоритма в массиве <tex>rep[i]</tex>, после выполнения алгоритма, будет содержаться перестановка, обратная перестановкаей.

'''int''' n = p.size; '''for''' i = 0 1 '''to''' n '''for''' j = 0 '''to''' n '''if''' p[j] == i + 1 rep[i] = j + 1; При представлении перестановки в виде циклов обратную перестановку можно легко получить, инвертировав все ребра в циклах. <tex> a = (1, 3, 2), (4, 5) \Rightarrow a^{-1} = (1, 2, 3), (4, 5) </tex> Отсюда следует более эффективный алгоритм, где <tex> visited[] </tex> - массив посещённых элементов: '''fun''' reversePerm (visited : '''boolean[]''', p : '''int[]''', rep : '''int[]''') '''int''' n = p.size; '''for''' i = 0 '''to''' n '''if''' visited[i] '''continue'''; ''<font color="green">// инвертировать цикл, начинающийся в позиции <tex> i </tex> </font>'' '''int''' last = i; '''int''' j = p[i]; '''while''' '''true''' '''int''' next = p[j]; p[j] = last; visited[j] = '''true'''; '''if''' j == i '''break'''; last = j; j = next;

<references /> ==Источники и литератураинформации==