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

begin i := n; s := true;

while (i > 0) and s do

begin s:=f[i] <= n-1; i := i-1 end;

TYPEJ :=s

end;

Непосредственно из определения вытекает следующий алгоритм построения таблицы инверсий для перестановки, заданной в естественной форме:

procedure TABIN (var f :TPE; var r :TPI);

Var I, j, k : integer;

begin for i := 1 to n do

begin k := f[i]; r[k] := 0;

for j := i-1 downto 1 do

{1} if f[j] > k then r[k] :=r[k]+1

end

end;

Временная сложность этого алгоритма фактически определяется числом выполнения {1}, которое равно n(n-1)/2, т. е. является О(n²).

Рассмотрим теперь алгоритм восстановления перестановки в естественной форме по его таблице инверсий. Здесь возможны два похода.

1. Будем последовательно, начиная с единицы и кончая n, расставлять элементы перестановки на свои места. Вначале всем вставляемым элементам перестановки соответствуют нулевые значения. Тогда для того чтобы определить место элемента i, достаточно перед ним оставить r_i нулей для элементов со значениями, большими i. Реализация этого подхода на языке Паскаль выглядит так:

type P = array [1..0] of 1..n;

. . .

procedure TABOUT1 (var r : TPI; var f : P);

var i, j, k : 0..n;

begin for i := 1 to n do f[i] := 0;

for i := 1 to n do

begin k := r[i]+1; j := 0;

repeat j := j+1;

if f[j] = 0 then k :=k-1

until k = 0;

f[j] := i

end

end;

Комментарий. Для параметра f определен новый тип P, отличающийся от типа TPE тем, что его элементы массива могут получать нулевые значения. После исполнения процедуры TABOUT1 параметр f принимает значения типа TPE. Переменная k служит для пропуска нулевых значений, а j - для определения места элемента i.

Упражнение. Исполните алгоритм TABOUT1 при n=5, r=/2,3,1,1,0/.

Оценим временную сложность алгоритма. Она определяется числом выполнения операторов внутри цикла repeat. Пусть T_i - точное число выполнения операторов внутри цикла для заданного i. Тогда r[i]+1  T_i  n. Если все перестановки из S_n равновероятны, то среднее значение r[i] равно (n-i)/2. Это приводит к тому, что вычислительная сложность этого алгоритма в среднем по всем перестановкам есть O(n²).

2. Запишем число n. Далее если r[n-1]=1, то значение n-1 поместим после n или перед ним, если r[n-1]=0. Предположим, что уже расставлены элементы n, n-1,..., i+1, тогда i нужно поставить после r[i] значений уже построенной последовательности.

Например, пусть n=5, r=/2,2,1,0,0/

1 шаг (постановка 5) r[5]=0 5

2 шаг (постановка 5) r[5]=0 4 5

3 шаг (постановка 5) r[5]=1 4 3 5

4 шаг (постановка 5) r[5]=2 4 3 2 5

5 шаг (постановка 5) r[5]=2 4 3 1 2 5

f = < 4 3 1 2 5>

В реализации этого алгоритма на языке Паскаль хранение формируемой последовательности естественней всего организовать в виде линейного цепного списка. В этом случае включение в список значения i сводится к вставке в него соответствующего элемента после r[i] ранее включенных элементов. Вследствие того, что каждое значение элементов списка лежит в промежутке от 1 до n, а число элементов не превосходит n, список удобно хранить в массиве (c) из n+1 ячейки. При этом в нулевой ячейке хранится значение первого элемента списка, а в ячейке с индексом i - значение элемента следующего в списке за ним. Для последнего включенного в список элемента перестановки и для не включенных значений соответствующие ячейки равны нулю.

Например, список 4325 при n=5 будет представлен c[0]=4, c[1]=0, c[2]=5, c[3]=2, c[4]=3, c[5]=0.

Реализация этого подхода на языке Паскаль выглядит так:

рrocedure TABOUT2 ( var r : :TPI; var f :TPE);