Генерация перестановок за минимальное число транспозиций.

При конструировании алгоритмов с использованием генерации перестановок, рассмотренные алгоритмы генерации в лексикографическом или антилексикографическом порядке иногда мало эффективны.

Пример. Пусть задана квадратная матрица вещественных чисел ||a_ij|| порядка n. Вычислить

åa[1,i₁]×a[2,i₂]×... ×a[n,i_n], (1)

где суммирование проводится по всем перестановкам <i₁ i₂ ... i_n> n-го порядка.

Выражение (1) называется перманентом [1] матрицы ||a_ij|| и весьма похоже на ее определитель. Заметим, что вычисление перманента или определителя непосредственно по определению имеет сложность O(n!), так как требуется генерация всех перестановок n-го порядка. Поэтому машинные алгоритмы вычисления определителей никогда не строятся непосредственно на его определении, а используют ряд его свойств, уменьшающих вычислительную сложность. Перманенты, однако, подобными свойствами не обладают, поэтому для их вычисления вполне приемлем подход, основанный на их определении. Остановимся на таком алгоритме подробнее.

Как уже отмечалось, подобный алгоритм требует генерирование всех перестановок n-го порядка. Однако генерация перестановок в лексикографическом или антилексикографическом порядке нецелесообразна. Здесь более желателен такой алгоритм генерирования, при котором каждая последующая перестановка отличалась бы от предыдущей на транспозиции только двух ее элементов.

Действительно, пусть последующая перестановка отличается от предыдущей на транспозиции [i_k,i_i], k¹j; тогда для того чтобы вычислить произведение, соответствующее последующей перестановке, не надо выполнять все n умножений, определяемые формулой (1), а достаточно, произведение, соответствующее, предыдущей, перестановке, умножить на a[j,i_j]/a[k,i_k], т. е. можно получить только за одно деление и умножение (считаем, что a[k,i_k]¹0).

Для полного решения поставленной в примере задачи покажем возможность алгоритма генерирования перестановок, в котором каждая последующая перестановка отличается от предыдущей на одну транспозицию. Опишем только такие из них, которые могут быть представлены по следующей рекурсивной схеме [2].

Пусть генерируемые элементы перестановки содержатся в массиве p[1],…,p[n] и имеется некоторая процедура PERM(m), генерирующая все перестановки элементов, хранящиеся в p[1],…,p[m], 1 £ m £ n, таким образом, что каждая последующая перестановка отличается от предыдущей одной транспозицией. Тогда генерирование перестановок n-го порядка может быть представлено как n обращений PERM(m-1), при условии, что при каждом очередном обращении элемент перестановки, хранящийся в p[n], заменяется на другой элемент из p[1],…,p[n-1] так, что элементы в p[n] не повторяются. В общем виде процедура PERM(m) может быть описана так:

procedure PERM(m: integer); {1 £ m £ n}

var i,k: integer;

{p, b – глобальные массивы}

begin

if m=1 then

{p[1], …, p[n] содержит новую перестановку}

for i:=1 to n do write (p[i])

else

for i:=1 to m do

begin PERM(m-1);

if i<m then

begin k:=p[m];

{*} p[m]:=p[b[m,i]];

p[b[m,i]]:=k

end

Дата добавления: 2014-01-04