Изменения
Более эффективный алгоритм получения обратной перестановки путем обращения циклов
<tex> a = (1, 3, 2), (4, 5) \Rightarrow a^{-1} = (1, 2, 3), (4, 5) </tex>
Отсюда следует более эффективный алгоритм (приведена in-place версия):
boolean[] visited = new boolean[n];
for (int i = 0; i < n; ++i)
{
if (visited[i]) continue;
// Reverse the cycle starting at i
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;
}
}
=Группа перестановок=
