Представление перестановок в циклической форме.

АЛГОРИТМЫ КОМБИНАТОРИКИ

Санкт-Петербург

оглавление

оглавление................................................................................................................................................................ 2

ТЕМА 1. ПЕРЕСТАНОВКИ КАК АБСТРАКТНЫЙ ТИП ДАННЫХ........................................................ 2

1.1 Представление перестановок в естественной форме........................................................................ 2

1.2 Представление перестановок в циклической форме......................................................................... 9

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

1.4 Задача о складывании карт................................................................................................................... 24

............................................................................................................................................................................... 58

Литература........................................................................................................................................................ 66

ТЕМА 1. ПЕРЕСТАНОВКИ КАК АБСТРАКТНЫЙ ТИП ДАННЫХ

Представление перестановок в естественной форме.

Перестановкой конечного множества X называется некоторое расположение его элементов в ряд. Будем считать X={1,...,n}, а множество всех перестановок этого множества обозначим S_n.

ПустьfÎS_n, fестественно отождествить с последовательностью <a₁ ... a_n>, где a_i=f(i). Это приводит к следующему представлению перестановок: f: array [1..n] of 1..n; f(i)=a_i ,которое в дальнейшем будем называть естественным.

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

Для перестановок в естественной форме описание типа выглядит так:

tpe= array [1..n] of 1..n; {*}

где n - глобальная константа, определяющая порядок перестановки, а ее верификационная функция имеет вид

function TYPEE ( var f : tpe) : Boolean;

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

i : integer { i<=n+1 } ;

Begin

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

i:=1;

while (i<=n) and a[f[i]] do

begin a[f[i]]:=false; i:=i+1 end;

TYPEE:=i=n+1

end;

Комментарий. Булевская функция TYPEE принимает значение true только в том случае, если все значения элементов f попарно различны между собой. Принадлежность значений элементов f диапазону 1..n обеспечена непосредственно описанием типа tpe.

Замечания. 1. Функция TYPEE имеет временную сложность O(n).

2. В дальнейшем принадлежность значения массива абстрактному типу данных - перестановка размерности n, представленная в естественной форме будет обозначаться идентификатором типа TPE, который будет использоваться при указании типа параметров процедур предлагаемых алгоритмов. Другими словами, идентификатор типа TPE, используемый в качестве описания типа параметра процедуры обозначает, что для передаваемого значения функция TYPEE вырабатывает значение true. В случае, если значение входного параметра не удовлетворяет истинности функции TYPEE, корректность процедуры не гарантирована.

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

Определение. Пусть f = <a₁ a₂ ... a_n>, g = <b₁ b₂ ... b_n>. Тогда перестановку g×f = g(f) = <c₁ c₂ ... c_n>, где c[i] = b[a_i], для i=1,...,n называют суперпозицией перестановок f и g; а перестановку f^-1 равную <d₁ d₂ ... d_n> так, что d[f_i]=i для i=1,...,n , называют обратной для f.

Упражнение. Докажите, что для любой перестановки f справедливо f×f^-1= f^-1×f= e = <1 ... n>.

В курсе алгебры обычно четность перестановки определяется через понятие инверсии элементов. Пусть f=<a₁ a₂ ... a_n>; говорят, что значения a_i и a_j, i,j=1,...,n, образуют инверсию, если из i<j следует a_i>a_j. Перестановку называют четной, если число инверсий в ней четно, и нечетной в противном случае. Четность перестановки может быть также определена как булевская функция, истинная для четных перестановок и ложная в противном случае; либо как функция знака перестановки sign(f)=(-1)^J⁽^f⁾, где J(f) - число инверсий в перестановке f. Относительно операции суперпозиции перестановки образуют группу, которая называется симметрической группой степени n, обозначается S_n, при этом e единица группы.

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

СУПЕРПОЗИЦИЯ. Алгоритм, реализующий суперпозицию перестановок непосредственно через определение, выглядит так:

procedure S(f:TPE; var g:TPE; var p:TPE);

var i:1..n;

begin for i:=1 to n do p[i]:=f[g[i]] end;

Замечания. 1. Алгоритм имеет временную сложность О(n).

2.Вызов параметра f как значения обусловлен тем, что значения f в общем случае должны быть сохранены до конца работы алгоритма.

ОБРАТНАЯ ПЕРЕСТАНОВКА. Алгоритм построения обратной перестановки p=f^-1 непосредственно по определению выглядит так:

procedure O(f: TPE; var p: TPE);

var i:1..n;

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

Замечание. Алгоритм имеет временную сложность O(n).

Представленный алгоритм для своей работы копирует перестановку f. Возникает вопрос, существует ли алгоритм трудоемкости O(n), формирующий обратную перестановку непосредственно на месте заданной. Ответ на него утвердителен:

procedure O1(var f: TPE);

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

Каждый цикл выписан на отдельной строчке. Внутри цикла следующим выписывается элемент перестановки являющейся образом в 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

Упражнение. Докажите свойство взаимосвязи разложений на циклы 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;

var i,j,k:1..n: a:array[1..n] of boolean;

s : boolean;

begin

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

for i:=1 to n do

if a[i] then

begin j:=f[i];

while j<>i do

begin s:= not s; a[j]:=false; j:=f[j] end

end;

ч1:=s

end;

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

Пусть перестановка f содержит k циклов следующего вида:

, для i=1,...,k,

Каждому такому циклу соответствует перестановка f_i = [ ], называемая также циклом длины n_i, которая определяется следующим образом:

f_i( )= ,...,f_i( )= ; f_i(x)=x для xÏ{ }.

Перестановку f можно представить в виде суперпозиции циклов

f = .

Например, f = <7 5 1 4 2 3 6>, тогда f = [1,7,6,3]×[2,5]×[4].

Замечание. 1. Элементы внутри одного цикла можно циклически переставлять местами.

Например: [1,7,6,3]=[7,6,3,1]=[6,3,1,7]=[3,1,7,6].

2. Представление f в виде суперпозиции коммутативно.

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

В дальнейших рассуждениях важную роль будут играть транспозиции соседних элементов, т. е. транспозиции вида [i,i+1], 1£i<n.

Упражнение. Докажите, что если f - транспозиция, то f=f^-1.

Перейдем к доказательству теоремы 1.

Лемма. Перестановку f=<a₁ ... a_n> можно представить в виде суперпозиции J(f) транспозиций соседних элементов.

Доказательство. Если t=[i,i+1], 1£i<n, то f×t=<a₁... a_i_-1a_i₊₁a_ia_i₊₂ ...a_n>. пусть t_i - число элементов в f, с которыми i образует инверсию, и расположенных передним. Тогда для того чтобы элемент 1 поставить на первое место, необходимо выполнить t₁ транспозиций соседних элементов; после этого для того чтобы элемент 2 поставить на второе место, необходимо выполнить t₂ транспозиций соседних элементов, и т. д. Таким образом, после t₁+...+t_т=J(f) шагов получим единичную перестановку - e, т. е. f×t₁×...×t_J₍_f₎=e, где t₁,...,t_J₍_f₎ -транспозиции соседних элементов.

Итак, f=(t₁×¼×t_J₍_f₎)^-1=t ×¼×t , что завершает доказательство леммы, так как t^-1=t для произвольной транспозиции t.

Лемма 2. Для произвольных перестановок f,gÎS_n

sgn(f×g)=sgn(f)×sgn(g).

Доказательство. 1) Пусть g=t=[i,i+1], 1£i<n, f=<a₁ ... a_n>; тогда f×g=<a₁,...,a_i-1a_i+1a_ia_i+1,...,a_n>

J(f×g)= ,

т. е. sgn(f×t) = -(-1)^J(f).

2) В случае произвольной перестановки g=t₁×¼×t_k, где t₁,...,t_k - транспозиции соседних элементов и k=J(g), имеем

sgn(f×g)=sgn(f×t₁×¼×t_k)=-sgn(f×t₁×¼×t_k_-1)=¼=(-1)^k×sgn(f)=sgn(g)×sgn(f).

Лемма 3. Каждая транспозиция есть нечетная перестановка.

Доказательство. Рассмотрим перестановку

<1 ... i-1 j i+1 ...j-1 i j+1 ...n>.

Ее можно преобразовать в единичную, произведя сначала j-i транспозиций [j-1,j], [j-2,j-1], ... ,[i,i+1] (i переводится на i-е место); затем (j-i)-1 транспозиций [i+1,i+2],[i+2,i+3], ... [i-1,j] (j переводится с i+1-го на j-е место). Это значит, что [i,j] может быть представлена в виде суперпозиции 2×(j-i)-1 транспозиций соседних элементов. По предыдущей лемме sgn([i,j])=(-1)²^×⁽^j^-ⁱ^)-1=-1.

Лемма 4. Знак произвольного цикла длины к равен (-1)^k^-1.

Доказательство. Заметим, что [a₁,...a_k]=[a₁,a₂]×[a₁,a₃]×¼×[a₁,a_k].

Доказательство теоремы 1 следует из леммы 4.

Замечание. Будем говорить, что перестановка f есть перестановка типа < >,если она содержит в разложении на циклы в точностиl_i циклов длины i (в случае если l_i=0, то обычно опускается). Определение знака перестановки через инверсии может быть дано для множеств, на которых задан линейный порядок. Однако знак перестановки зависит только от ее типа, а не от порядка, определенного на X.

Представление перестановок в циклической форме.

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

f = [3 1 6 7]×[5 4]×[2] = [-3 1 6 7-5 4-2].

В этом случае описание типа перестановки должно выглядеть так:

tpc= array [1..n] of -n..n;

Упражнение. 1.Опишите верификационную функцию абстрактного типа TPC с заголовком:

function TYPEC (var f : TPC) : Boolean;

Указание. Здесь нужно проверить, что модуль всех значений элементов перестановки должны быть различны и что первый элемент отрицательный.

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

procedure TRSL(var f: TPE; var g: TPC);

переводящую перестановку f из естественной формы в циклическую (перестановка g).

Среди алгоритмов, связанных с выполнением операций суперпозиции и нахождение обратной перестановки, наиболее интересным, является алгоритм вычисления g(f) в случае, когда f представлена в естественной форме, а g - в циклической. При этом считаем, что результат этой суперпозиции формируется на месте перестановки f.

Разберем этот алгоритм сначала на примере.

Пусть f=<3 5 6 2 4 7 1>, g=[-6 2 3 -5 4 1 7], тогда для вычисления g(f) обычно поступают следующим образом. Элемент 1 в f переходит в 3, а в g элемент 3 отображается в 6, т. е. в перестановке g(f) 1 сопоставляется значение 6. Далее, элемент 2 в f переходит в 5, а в g элемент 5 отображается в 4, т. е. в g(f) 2 сопоставляется значение 4. В общем случае для sÎ1,...,n выбираем значение f(s), затем совершаем поиск месторасположение значение f(s) в g; выясняем, в какое значение переходит f(s) в g и сопоставляем аргументу s значение g(f(s)). Непосредственная реализация этого алгоритма требует:

1) поиск индекса значения f(s) в массиве, соответствующем перестановке g;

2) если значение f(s) в массиве g записано последним элементом цикла, к которому принадлежит f(s), то необходимо совершить поиск индекса первого элемента этого цикла для того, чтобы вычислить g(f(s)).

Заметим, что выбор значения s можно производить произвольным образом. В частности так, что f(s) принимает значение g(n), g(n-1),...,g(1). При таком переборе значений s элементы циклов, записанные в массиве g последними, всегда обрабатываются раньше элементов этих же циклов записанных первыми. Поэтому формирование значений g(f) для s, соответствующих последним элементам циклов g, может производиться при обработке первых элементов этих же циклов. С другой стороны, такой перебор ничем не хуже перебора, когда s принимает значения 1,...,n, так как при одном подходе нам необходимо по значению s определять индекс f(s) в массиве g, а при другом подходе по значению g(i), i меняется n, n-1,...,1, определять индекс этого значения в массиве f.

Реализация такого алгоритма на языке Паскаль может выглядеть так:

procedure U(var f:TPE; var g: TPC); {f=g×f}

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

begin k:=0; {0 помечает последние элементы циклов g}

{3} for i:=n downto 1 do

begin j:= abs(g[i]);

{2} s:=1; while j<> f[s] do s:=s+1;

f[s]:=k;

if g[i]<0 then

begin

{1} s:= 1; while f[s] <> 0 do s:=s+1;

f[s]:=j; k:=0

end

else k:=j

end

end;

Комментарий. Переменная i служит для перебора элементов g; k определяет значение, заносимое в f на текущем шаге; j - значение, корректируемое в f на текущем шаге; s - индекс элемента j в f.

Замечание. В процессе исполнения процедуры U элементы массива f могут принимать нулевые значения, что, вообще говоря, недопустимо по описанию абстрактного типа TPE. Однако, мы будем допускать такого рода неточности, когда при исполнении процедуры допускается расширение множества значений типа, каждый раз оговаривая подобные случаи. При этом считаем, что такие расширения недопустимы на входе и выходе процедуры.

Нетрудно видеть, что временная вычислительная сложность этого алгоритма есть О( ), если считать месторасположение конкретных значений элементов равновероятным; m - число циклов в перестановке. Оценим число циклов в перестановке.

ТЕОРЕМА 2. Общее число циклов во всех n! перестановках

n-го порядка равно n!´H_n, где H_n= .

Доказательство. Пусть все n! перестановок записаны в циклической форме. Зафиксируем i, 1£i£n, и рассмотрим, сколько циклов длины i встречается во всех этих перестановках.

Заметим, что конкретный цикл [a₁,...,a_i] встречается в (n-i)! перестановках, так как это число способов, которыми можно переставить оставшиеся n-i элементов.

Число различных возможных циклов [a₁,...,a_i] есть n´(n-1)´¼´(n-i)/i, так как элемент a₁ можно выбрать n способами, элементами a₂ - (n-1) способами и т. д.; а среди n´(n-1)´¼´(n-i+1) циклов из a₁,...,a_i фиксированных элементов появляется i раз, как [а₁,...,а_i], [a₂,...,a_i,a₁],...,[a_i,a₁,...,a_i_-1]. Поэтому общее число циклов из i элементов во всех n! перестановках есть n´(n-1)´¼´(n-i+1)/i, взятое (n-i)! раз, т. е. n!/i.

Суммируя по всем i, получаем общее число циклов во всех n! перестановках =n!´H_n.

Таким образом, временная вычислительная сложность алгоритма U есть n´(n+H_n)/2.

Следствие. Из теоремы 2 следует, что на одну перестановку в среднем приходится H_n циклов.

Упражнение. Модернизируйте алгоритм U так, чтобы исключить поиск в f индекса нулевого значения ( строка {1}).

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

Замечание. Для случая преобразования перестановки g в естественную форму алгоритм U может быть упрощен за счет удаления операторов ассоциативного поиска в f индекса j (строка {2}). Проведя две указанные модернизации, можно построить алгоритм перевода с вычислительной сложностью О(n).

Упражнение. Реализуйте подобный алгоритм.

Рассмотрим алгоритм вычисления обратной перестановки для перестановок, заданных в циклической форме. Учитывая, что обратная перестановка получается за счет переориентации ребер графа перестановки, заметим, что обратная перестановка в циклической форме может быть построена путем ‘симметричного отражения перестановки относительно ее конца’, исключая начальный знак ‘ - ’.

Например, f=[-6 2 3 -5 4 1 7] : [-7 1 4 5 -3 2 6]=f^-1.

Алгоритм, реализующий этот процесс, может быть представлен таким образом:

procedure O2( var f:TPC);

var i : 1..n; k : -n..n;

begin f[1]:=-f[1];

for i:=2 to n do

if f[i]<0 then begin f[i]:=-f[i]; f[i-1]:=f[i-1] end;

for i:=1 to n div 2 do

begin k:=f[i]; f[i]:=f[n-i+1]; f[n-i+1]:=k end;

f[1]:=-f[1]

end;

Упражнение. Перепишите алгоритм U, чтобы он выполнял вычисление g^-1×f. Указание. Обратите внимание на оператор {3}.

Алгоритм определения знака для перестановок, заданных в циклической форме, легко реализуется на основе теоремы 1:

function ч2 (var f : TPC): Boolean;

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. Напишите процедуру:

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 равновероятны.

12 3

Не нашли, что искали? Воспользуйтесь поиском по сайту:

©2015 - 2024 stydopedia.ru Все материалы защищены законодательством РФ.