Var I : 1..N; s : Boolean;

begin s:=true;

for i:=1 to n do

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

ч2:=s

end;

Оба алгоритма О2 и Ч2 имеет временную сложность О(n).

Наряду с представлением перестановок в циклической форме с помощью разметки начала циклов, возможна несколько иная форма представления циклических перестановок.

Определение. Будем говорить, что перестановка, представленная в виде разложения на циклы, находится в канонической форме, если:

а) обязательно записываются все циклы;

б) в каждом цикле первым записывается элемент с наименьшим значением;

в) циклы располагаются в порядке убывания значений первых элементов.

Например, f=[3 1 6 7][5 4] представляется как [4 5][2][1 6 7 3].

Скобочная структура в канонической форме может быть опущена, так как первым элементам циклов соответствуют левосторонние локальные минимумы (a_k, ikn, является левосторонним локальным минимумом f, если a_i<a_i, 1i<k).

В приведенном примере перестановка f может быть записана как (4 5 2 1 6 7 3), где круглые скобки указывают, что перестановка представлена в канонической форме.

Упражнение. Пусть f=<a₁ ... a_n>, g=(a₁ ... a_n),n1. Докажите, что fg.

Абстрактный тип ‘перестановка в канонической форме’(TPK) на языке Паскаль может быть описан так

tpk= array [1..n] of 1..n; {описание типа }

и верификационной функцией, совпадающей с верификационной функцией представления перестановок в естественной форме (function TYPEE была описана выше). Заметим, что абстрактные типы TPE и TPK имеют различные семантики.

Рассмотрим алгоритм перевода из естественного представления перестановки в каноническую форму:

procedure CANON(var f : TPE; var g : TPK);

var i,j : 0..n;

a : array [1..n] of Boolean;

procedure B(k : integer);

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

if k<>i then

begin

B(f[k]);

g[j]:=k; j:=j-1; {2}

end

end;

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

for i:=1 to n do

If a[I] then

begin {3}

B(f[i]);

g[j]:=i; j:=j-1 {4}

end

end;

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

{3}	i=1	j=7
{1}	i=1	j=7	k=6	a[6]=false
{1}	i=1	j=7	k=7	a[7]=false
{1}	i=1	j=7	k=3	a[3]=false
{1}	i=1	j=7	k=1	a[1]=false
{2}	i=1	j=6	k=3	g[7]=3
{2}	i=1	j=5	k=7	g[6]=7
{2}	i=1	j=4	k=6	g[5]=6
{4}	i=1	j=3		g[4]=1
{3}	i=2	j=3
{1}	i=2	j=3	k=2	a[2]=false
{4}	i=2	j=2		g[3]=2
{3}	i=4	j=2
{1}	i=4	j=2	k=5	a[5]=false
{1}	i=4	j=2	k=4	a[4]=false
{2}	i=4	j=1	k=5	g[2]=5
{4}	i=4	j=0		g[1]=4

т. е. g = (4 5 2 1 6 7 3)

Работа алгоритма происходит следующим образом. Подобно алгоритму O1, в каждом цикле первым выбирается элемент с наименьшим значением (переменная i в точке {3}), при этом циклы следуют в порядке возрастания наименьших элементов. За счет рекурсивного вызова процедуры B осуществляется движение по каждому конкретному циклу до его замыкания. При этом глубина рекурсии равна числу элементов цикла. По выходу из каждого очередного уровня рекурсии в массив g заносится текущее значение цикла (точки {2},{4}), при этом массив g заполняется, начиная с больших значений индекса.

Нетрудно видеть, что процедура CANON имеет временную сложность О(n).

Упражнения.

1. Напишите вариант алгоритма CANON без использования рекурсии.

2. Напишите процедуру: