Procedure u1(var f : tpe; var g : tpk);

вычисляющую f=g^-1f, если f задана в естественной форме, а g – в канонической.

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

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

. . .

const n =...;

type m = array [1..n] of real;

function INDEX (var a : m) : real;

Var r : real;

begin r:=a[1]; INDEX:=1;

for i:=2 to n do

if a[i]<r then

begin r:=a[i]; INDEX:=i end {1}

end;

. . .

Возникает естественный вопрос: ‘ Сколько раз в среднем в этом фрагменте программы выполняется оператор {1}, если считать распределения значений элементов в массиве a равновероятным?’.

Заметим, что оператор {1} выполняется только при таких i, когда значение a[i] является левосторонним минимумом, т. е. по теореме 2, оператор {1} выполняется H_n-1 раз.

Упражнение. Оцените среднее число выполнения оператора {1}, если в массиве a допускают равные значения элементов, причем значение индекса должно быть максимально возможным. Как и в примере, считаем, что все возможные распределения значений элементов в a равновероятны.

1.3 Представление перестановок в виде таблицы инверсий.

Определение. Таблицей инверсий перестановки f = <a₁ ... a_n> называется последовательность чисел r₁,...,r_n, где r_i, 1  i  n, равно числу элементов, больших i и расположенных перед ним. Таблицу инверсий будем обозначать /r₁,...,r_n/.

Например, f = <5 1 2 6 4 7 3> r =/1,1,4,2,0,0,0/.

По определению: 0  r₁  n-1

0  r₂  n-2

. . .

0  r_n-1  1

r_{n =} 0.

Упражнение. Пусть f = <a₁ ... a_n>, ее таблица инверсий /r₁,...,r_n/. Как выглядит таблицей инверсий перестановки f=<a_n ... a₁>?

Замечание. Наряду с таблицей инверсии перестановки f можно рассмотреть таблицу r,...,r антиинверсий перестановки f, где r определяется как число элементов f, меньших i и расположенных перед ним.

Теорема 3. Последовательность чисел r₁+r+1, r₂+r+1,..., r_n+r+1 образует обратную перестановку к f.

Доказательство следует из определения обратной перестановки.

Пусть q[i] (q`[i]), 1  i  n, обозначает число элементов перестановки f, больших (меньших) i и расположенных после него. Тогда из определения также следует

q[i]+r[i] = n-i

q’[i]+r`[i] = i-1

q[i]+q`[i] = n-1-f^-1[i]

Например, f = <5 1 2 6 4 7 3>

r = 1,1,4,2,0,0,0, r` = 0,1,2,2,0,3,5,

q = 5,5,0,1,2,1,0, q` = 0,0,0,1,4,2,1.

Следствие. Если определена какая-нибудь одна из четырех таблиц r, r`, q, q`, то из указанных соотношений легко вычисляются и три других.

Упражнение. Докажите, что для заданной перестановки f, соответствующая ей таблица инверсий определяется однозначно. Указание. Воспользуйтесь следующим соотношением: пусть перестановка <a₁ ... a_n>, (n-1) порядка соответствует /r₁,...,r_n-1/, тогда перестановке <a₁ ... a_i n а_i+1 ... a_n> соответствует таблица инверсий /r,...,r,0/, где r=r_k, если k{a₁ ... a_i} и r= r_k+1, если k{a_i+1 ... a_n}.

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

tpi= array [1..n] of 0..n;

для конкретных значений которого истинна следующая верификационная функция:

function TYPEJ (var f tpi:) : Boolean;