С помощью векторов инверсий.

↑

▷ Содержание

⇐ ПредыдущаяСтр 9 из 10Следующая ⇒

Пара (αi, αj) называется инверсией перестановки α = (α1, α2,..., αn), если i < j и αi > αj. Инверсию (αi, αj) будем также называть j-инверсией перестановки α, тем самым явно указывая номер меньшего элемента в инверсии (αi, αj).

Вектором инверсий перестановки α ∈ Sn называется последовательность целых чисел (d1, d2,..., dn) такая, что dj есть число j-инверсий перестановки α. Другими словами, dj есть число элементов перестановки α, больших αj и находящихся левее αj в последовательности (α1,..., αn), dj =| {αi | i < j & αi > αj} | 12.

Например, для перестановки (4, 3, 5, 2, 1, 7, 8, 6, 9) вектором инверсий будет вектор (0, 1, 0, 3, 4, 0, 0, 2, 0).

Вектор инверсий содержит информацию о структуре "беспорядка" перестановки. Такая информация оказывается полезной при разработке различных алгоритмов обработки данных.

Процесс восстановления перестановки α = (α 1 ,..., α 5), имеющей вектор инверсий d = (0, 0, 2, 1, 1), выглядит так:

i = 5, I5 = {1, 2, 3, 4, 5}, d5 + 1 = 2, α5 = 4;

i = 4, I4 = {1, 2, 3, 5}, d4 + 1 = 2, α4 = 3;

i = 3, I3 = {1, 2, 5}, d3 + 1 = 3, α3 = 1;

i = 2, I2 = {2, 5}, d2 + 1 = 1, α2 = 5;

i = 1, I1 = {2}, d1 + 1 = 1, α1 = 2;

α = (2, 5, 1, 3, 4).

Формализуем данный алгоритм в виде псевдокода. Очевидным образом можно сэкономить используемую память и уменьшить число операций, отказавшись от создания множества Ii и упорядочивания его элементов на каждом шаге i. Вместо этого достаточно хранить только лишь метки для уже вычеркнутых чисел из множества { 1, 2 ,..., n} и добавлять на шаге i метку для числа αi. Будем использовать массив ϕ размерности n с булевыми значениями его элементов true и false для создания таких меток.

Алгоритм PConstrV (d1 ,..., dn) восстановления перестановки:

α = (α1,..., αn) по ее вектору инверсий d = (d1,..., dn)

for k = 1 to n do ϕk:= true;

for i = n downto 1 do

begin

j:= 1;

m:= n;

while j ≤ di or ϕm = false do

begin

if ϕj = true then j:= j + 1;

m:= m − 1

end;

αi:= m;

ϕm:= false

end.

Алгоритм PV Inv(n) генерации всех перестановок через векторы инверсий:

for i = 0 to n! − 1 do

begin % нахождение n-факториального

FDecomp(n, i); % представления (d1,..., dn) числа i;

PConstrV (d1,..., dn); % восстановление перестановки α по

write(α1,..., αn) % вектору инверсий (d1,..., dn)

end.

С помощью вложенных циклов.

Будем говорить, что перестановка является циклом длины k степени d, если ее элементы , получены из 1, 2, …, k циклическим сдвигом вправо на d позиций, остальные n – k элементов стационарны. Например, подстановка является циклом длины 4 степени 1.

Алгоритм порождения подстановок с помощью вложенных циклов основан на следующей теореме.

Любую подстановку на множестве можно представить в виде композиции , где — циклическая подстановка порядка i.

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

Цикл ()

;

Конец цикла

Пока ()

Печать

Сдвиг первых k элементов на одну позицию

Пока ( и )

Сдвиг первых k элементов на одну позицию

Конец цикла

Конец цикла

Конец

В порядке минимального изменения.

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

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

procedure Perm(m:integer);

{Основная процедура генерирования и вывода очередной перестановки}

var

k,k1,i:integer;

begin

if m=1 then {Нерекурсивная ветвь}

begin

for i:=1 to n do

Write(P[i]:4);

Writeln;

end

else {Рекурсивная ветвь}

for i:=1 to m do

begin

Perm(m-1);

if i<m then

begin

k1:=b(m,i);

k:=P[k1];

P[k1]:=P[m];

P[m]:=k;

end;

end;

end;

Познавательные статьи:



Организация работы процедурного кабинета

Статус республик в составе РФ

Понятие финансов, их функции и особенности

Сущность демографической политии