Var I, j, k, m:1..N; a:array[1..N] of Boolean;

begin

for i:=1 to n do a[i]:=true;

for i:= 1 to n do

If a[I] then

begin j:=f[i]; a[i]:=false; k:=i; {1}

while j<>i do

begin m:=f[j]; f[j]:=k; k:=j; j:=m; a[k]:=false {2}

end;

f[i]:=k {3}

end;

end {4} ;

Тест f=<5 7 3 1 6 4 2>

{1} i=1 j=5 a[1]=false k=1 m – не определено

{2} m=6 f[5]=1 k=5 j=6 a[5]=false

{2} m=4 f[6]=5 k=6 j=4 a[6]=false

{2} m=1 f[4]=6 k=4 j=1 a[4]=false

{3} f[1]=4

{1} i=2 j=7 a[2]=false k=2 m=1

{2} m=2 f[7]=2 k=7 j=2 a[7]=false

{3} f[2]=7

{1} i=3 j=3 a[3]=false k=3 m=2

{3} f[3]=3

{4} f=<4 7 3 6 1 5 2>

<5 7 3 1 6 4 2>^.<4 7 3 6 1 5 2>=<1 2 3 4 5 6 7>

Доказательство правильности реализации алгоритма основано на том, что перестановки f и f^-1 имеют взаимосвязанные структуры при разложении их на циклы.

Пример. Разложение перестановки на циклы.

f=<5 7 3 1 6 4 2>

1564

27

3

Каждый цикл выписан на отдельной строчке. Внутри цикла следующим выписывается элемент перестановки являющейся образом в f текущего, т. е. xf(x). Образ последнего элемента совпадает с первым. В этом примере первым в каждом цикле выписан элемент с наименьшим номером внутри цикла, a циклы расположены в порядке возрастания первых элементов.

Для того чтобы получить разложение на циклы обратной для f перестановки, достаточно перевернуть “стрелочки” в каждом цикле разложения f в обратную сторону.

Пример.Разложение на циклы обратной перестановки.

f ^-1=<5 7 3 1 6 4 2>^-1=<4 7 3 6 1 5 2>

1465

27

3

Упражнение. Докажите свойство взаимосвязи разложений на циклы f и f^-1 для произвольной перестановки из S_n.

В приведенном алгоритме массив a служит для пометки включенных в циклы элементов f. В каждом цикле первым выбирается элемент, имеющий наименьший номер (второй оператор цикла типа for). Обход каждого цикла с переориентацией стрелок осуществляется оператором цикла типа while.

ЧЕТНОСТЬ ПЕРЕСТАНОВКИ. Алгоритм вычисления четности перестановки непосредственно по определению может быть представлен следующем образом:

function Ч(var. f: TPE): boolean;

Var I,j:1..N; s:boolean:

begin s:=true;

for i:=2 to n do

for j:=1 to i-1 do

if f[j]>f[i] then s:=not s;

Ч:=s

end;

Этот алгоритм имеет временную вычислительную сложность О(n²). Однако оказывается, что существует алгоритм определения четности перестановки со сложностью О(n). Такой алгоритм также строится на анализе свойств циклической структуры перестановки на основе следующей теоремы:

Теорема 1. Перестановка f является четной тогда и только тогда когда и в ее циклическом разложении число циклов четной длины четно.

Здесь под длиною цикла понимается число элементов перестановки, входящих в данный цикл.

На основе этой теоремы алгоритм определения четности перестановки может быть реализован по схеме процедуры O1 с изменениями некоторых действий внутри цикла while.

Function ч1 (var f: TPE) : boolean;