Из текста процедуры видно, что элемент p[m] после i-го вызова процедуры PERM(m-1) заменяется элементом p[b[m,i]]. Для того чтобы эта схема работала правильно, мы должны определить массив bm так, чтобы гарантировать, что каждая транспозиция {*} вводит новый элемент в p[m]. Как корректно построить матрицу bm?
Это может быть сделано рекурсивно. Предположим, что уже построена матрица
bm= ,
удовлетворяющая требуемым условиям. Заметим, что значения элементов b[j,i], 1£j£n, произвольны (их, в дальнейшем будем обозначать ·). Для построения матрицы bm+1 достаточно определить элементы b[m+1,1], b[m+1,2], …, b[m+1,m]. Обозначим jm следующую перестановку чисел 1,…,m:
jm(i) = индекс j, такой что p[j] содержит начальное
значение переменной p[i] после выполнения perm(m).
Тогда в качестве b[m+1,1] можно взять любое значение из 1,…,m, пусть это будет k1. В качестве b[m+1,2] – любое значение из 1,…,m, отличное от jm(k1); пусть это будет k2. В качестве b[m+1,3] – любое значение из 1,…,m, отличное от jm(jm(k1)) = j(k1) и jm(k2); пусть это будет k3, и т. д. В качестве b[m+1,m] окажется единственное значение из 1,…,m, отличное от j(k1), j(k2),…, jm(km-1).
Пример
b1 = , b2 = , b3 = , b4 = .
Если в начальный момент в массиве p записана перестановка <1 2 3 4>, то после обращения к процедуре perm(4) с матрицей b4 перестановки генерируются в следующем порядке:
Упражнение. Исходя из матрицы b3 постройте матрицу b4 таким образом, чтобы первой генерировалась перестановка <1 2 3 4>, а последней 24-ой перестановка <4 1 2 3>.
Определения. 1. Будем говорить, что матрицы генерирования перестановок bn и bэквивалентны, если у них соответственно совпадают элементы, лежащие ниже главной диагонали.
2. Будем говорить, что две процедуры генерирования перестановок эквивалентны, если исходя из начальной перестановки <1 2 … n>, они генерируют все другие перестановки в одном и том же порядке.
Упражнения. 1.Доказать, что процедуры perm с двумя неэквивалентными матрицами генерирования не эквивалентны.
2. Доказать, что число Тn неэквивалентных матриц генерирования порядка n равно .
Из упражнения 2 следует, что рекурсивными схемами могут быть описаны Тn способов генерирования перестановок из единичной перестановки n-го порядка при условии, что каждая последующая перестановка отличается от предыдущей ровно на одну транспозицию.
Замечание. При описании матрицы bm в виде двухмерного массива больше половины ее элементов (т. е. элементов bij,для которых j£i) не используются процедурой perm. Поэтому для экономии памяти вместо двухмерной матрицы bm можно использовать одномерный массив b1 размером m(m-1)/2.
Упражнение. Модернизируйте процедуру perm таким образом, чтобы вместо двухмерного массива bm использовался бы одномерный массив b1, в котором необходимые для генерации элементы располагались в порядке b21,b31,b32,…,bn1,bn2,…,bnn-1.
Наряду с представлением bm в виде массива часто бывает удобно задавать элементы bm динамически как значения соответствующей функции от m и i.
Пример.
Function b(m,i :integer) : integer; {m>i}
begin
if (m mod 2 = 0) and m > 2 then
if i < m-1 then b:=1 else b:=m-2
else b:=m-1
end;
Упражнение. Построить матрицу b5, соответствующую функции b и доказать, что процедура perm с использованием этой матрицы работает корректно. Обобщить полученный результат для произвольного n(Подробно такое доказательство рассмотрено в [2], там же приведены другие функциональные представления b(m,i).).
Алгоритмы генерирования, построенные по схеме процедуры perm, удобно применять также для генерации перестановок, удовлетворяющих заданным свойствам.
Упражнение. Модернизируйте процедуру perm, чтобы она генерировала все возможные ‘беспорядки’ чисел 1,...,n, т.е. такие перестановки, в которых для любого i, 1£i£n, p[i]¹i.
Возникает естественный вопрос, существует ли генерации перестановок, в которых каждая последующая отличается от предыдущей на транспозицию, и которые не описываются схемой процедуры perm? Ответ на этот вопрос утвердителен.
Нетрудно видеть, что представленная генерация обладает тем свойством, что каждая последующая перестановка в ней отличается от предыдущей на одну транспозицию соседних элементов. Кроме того, приведенная генерация легко обобщается на случай произвольного n. А именно каждая перестановка (n-1)-го порядка имеет n позиций, куда может быть помещен элемент n, чтобы получить перестановку n -го порядка ( n-1 позиция перед каждым элементом заданной перестановки и 1 - после последнего). Предположим, что построена последовательность перестановок элементов 1,2,...,n-1, аналогичная приведенной. Тогда требуемую последовательность перестановок элементов 1,2,...,n можно получить, вставляя элемент n всеми возможными способами в каждую перестановку элементов 1,2,...,n-1. При этом n перемещается между последней и первой позициями попеременно назад и вперед (n-1)! раз.
Упражнение. Показать, что перестановка <4 1 5 6 3 2> непосредственно следует за перестановкой <4 1 5 3 6 2>. Как выглядят две последние перестановки в генерации n-го порядка?
Покажем, что такая генерация не может быть получена никаким вариантом процедуры perm. Для этого заметим, что при генерации процедурой perm каждое конкретное значение хранится в p[n] в (n-1)! последовательных перестановках, а приведенной генерации каждое конкретное значение сохраняется в p[n] не более чем (n-1)-й последовательной перестановке.
Упражнение. Доказать, что для произвольного n не существует варианта процедуры perm, в котором генерация каждой последующей перестановки получается одной транспозицией соседних элементов в предыдущей.
Перейдем теперь к разработке программы генерации перестановок с помощью одной транспозиции соседних элементов. Приведенная выше генерация получена по рекурсивной схеме, однако непосредственная реализация этой схемы имеет существенный недостаток: для генерации всех перестановок n -го порядка требуется хранение всех перестановок (n-1)-го порядка. То есть подобный алгоритм имеет емкостную вычислительную сложность O((n-1)!). Для того чтобы уменьшить емкостные характеристики этой схемы, воспользуемся аналогичным приемом, который был применен для построения нерекурсивного варианта генерации перестановок в лексикографическом порядке.
Предположим, что уже сгенерирована перестановка <a1 ... an>, удовлетворяющая необходимым требованиям; тогда для того чтобы построить следующую перестановку, нужно определить элемент ak, 1£k£n, который перемещается на новую позицию, и направление перемещения. Направление перемещения можно контролировать с помощью специального вектора d длины n, i-я координата которого принимает значение 1, если элемент i перемещается вперед (от позиций с меньшими номерами к большим), и -1, если элемент i перемещается назад. Изменение значения координаты происходит тогда, когда элемент i достигает крайних позиций.
Нетрудно видеть, что перемещаемым является элемент с наибольшим номером, который еще не достиг своего крайнего положения в направлении своего перемещения; т.е. если мы удалим из перестановки все элементы со значениями больше ak, то в оставшейся перестановки ak-го порядка возможно перемещение этого элемента в соответствующем ему направлении. Для удобства реализации этого условия вместо перестановки <a1 ... an> будем рассматривать вектор длины n+2, следующего вида <n+1,a1,....an,n+1>. В этом случае перемещаемым в перестановке <a1 ... an> является элемент с наибольшим номером, перед которым в направлении перемещения не стоит элемент с большим значением. Для быстрого поиска месторасположения в перестановке элемента с конкретным значением введем в программу генерации также перестановку r, обратную к <a1 ... an>. Тогда программа генерации выглядит так:
Упражнения. 1. Доказать, что условием окончания генерирования всех перестановок является то, что перемещаемым становиться элемент 1.
2. Показать, что операторы строки {*} выполняются раз. Определить временную вычислительную сложность алгоритма. Какова его емкостная вычислительная сложность?
3. Написать программу, которая генерирует перестановки с помощью одной транспозиции соседних элементов и при n=4 выдает следующую последовательность:
Кроме приведенных алгоритмов генерации перестановок, возможны алгоритмы, основанные на других характеристических свойствах упорядочивания. Например, перестановки могут быть упорядочены с учетом числа циклов или инверсий и т.п. такие алгоритмы достаточно специфичны и здесь не рассматриваются. Классы перестановок с фиксированным числом циклов или инверсий представляют большой интерес в перечислительной комбинаторике и при анализе алгоритмов.
При программировании на языке Паскаль возможны два подхода к представлению подмножеств конечного множества. В первом, основанном на использовании структурного типа SET OF, базовый тип (элементы множества) задается некоторым простым типом. При этом пользователь может давать имена элементам множества, определять их упорядоченность и применять операции, допустимые над множествами языка Паскаль. Второй подход основан на том, что пользователь интерпретирует множества с помощью других типов, чаще всего массивов. В этом случае, элементы множества трактуются как элементы массива, они могут считаться как упорядоченные, например, по упорядоченности индекса, а выполняемые над ними операции определяются применяемыми операторами или процедурами. Возможна также интерпретация множеств в виде списочных структур. Отметим, что второй подход естественен, когда по условию программируемой задачи элементы сами по себе имеют сложную структуру.
Следует отметить, что описания множеств с использованием типа SET OF фактически сводится к представлению множеств в виде упакованных булевских массивов и реализация соответствующих операций над ними. Но для удобства пользователя все это выполняется в процессе трансляции программы.
Для того чтобы более точно описать проблемы, возникающие в нижеописанных алгоритмах, будем считать, что базовое множество содержит n элементов, а каждое конкретное его подмножество представляется в виде массива. При этом i-й элемент массива принимает значение 1, если i-й базовый элемент (1 £ i £ n) принадлежит множеству, и нулю в противном случае (сравните с понятием характеристической функции множества, используемое в математике). Кроме того, считаем, что упорядоченность элементов множества соответствует упорядоченности индексов массива. Будем изображать множества в виде кортежей из n нулей и единиц.
Пример. X=(1,0,0,0,1,1) означает, что базовое множество содержит шесть упорядоченных элементов, а в множество X включены первый, пятый и шестой по порядку элементы. Пустое множество в этом случае представляется (0,0,0,0,0,0), а множество всех элементов (1,1,1,1,1,1).
Первой рассмотрим задачу генерации всех подмножеств данного множества. Здесь как и с перестановками наиболее распространенными являются генерирование подмножеств в лексикографическом порядке и генерирование, при котором каждое последующее подмножество отличается от предыдущего вставкой или удалением одного элемента.
Определение. Пусть A=(x1,…,xn) и B=(y1,…,yn), xi,yiÎ{0,1}, 1£i£n. Будем говорить, что множество А предшествует множеству B лексикографическом порядке ,если существует i, 1£i£n, xi<yi и xj=yj для любого j, 1£j<i; обозначим это А<B.
Упражнение. Пусть 0 £ a < b <2n, a, b - натуральные; представим a и b в двоичной системе с выписыванием всех n двоичных разрядов и пусть a = и b = . Доказать, что тогда (x1,...,xn) < (y1,...,yn).
Основываясь на результате упражнения, можно написать следующую программу генерации всех подмножеств данного множества в лексикографическом порядке.
program SET1(, output);
const n= ; n1= ; {n1=n+1}
var s : array [1..n1] of 0..1;
i,j : integer;
begin
for i:=1 to n1 do s[i]:=0;
while s[n1]=0 do
begin
for i:=1 to n do write(s[i]); writeln;
i:=1;
{**} while s[i]=1 do
begin s[i]:=0; i:=i+1 end;
{*} s[i]:=1
end
end.
Комментарий. Пусть множеству s соответствует число s, тогда множеству, следующему за s, соответствует число s+1.
2. Показать, что условие цикла {**} проверяется 2n+1-1 раз.
3. Определить вычислительную сложность алгоритма.
4. Написать программу генерации всех подмножеств в лексикографическом порядке, если s описано как SET OF 1..n.
Замечания. 1.Следует отметить, что в системе команд любой вычислительной машины имеются команды, выполняющие арифметическое сложение двоичных последовательностей определенной длин, таких, как 8 бит - 1 байт, 16 - 2 байта и тому подобное. Кроме того, часто имеются специальные программные конструкции (например, макрокоманды, выполняющие сложение более длинных двоичных последовательностей). Непосредственное применение таких команд в программе SET1 может существенно улучшить ее временные характеристики.
2. Для построения других алгоритмов генерации подмножеств, представляет интерес свойства последовательности значений переменной i перед исполнением оператора {*}. Заметим, что этот оператор {*} исполняется 2n раз, при этом последнее значение i=n+1 приводит к окончанию генерации всех подмножеств для множества из n-элементов. Пусть In обозначает эту последовательность значений переменной i за исключением последнего. In можно трактовать как последовательность номеров позиций младшей единицы в двоичном разложении чисел 1, 2, ..., 2n-1. По построению двоичной позиционной системы последовательность In удовлетворяет следующему рекурсивному определению
I1=1, In= In-1,n, In-1
(первый раз единица в n-ой позиции появляется для числа 2n-1, при этом во всех других позициях с 1-ой по (n-1)-ую значения становятся нулевыми, затем для чисел 2n-1+1,..., 2n-1 повторяется процесс заполнения единицами позиций с номерами меньшими n).
Упражнение. Доказать, что если In-1=i1, i2, ..., i, n>1, то In=1, i1+1, 1, i2+1, 1, ..., i+1, 1.
bm=
,
(k1) и jm(k2); пусть это будет k3, и т. д. В качестве b[m+1,m] окажется единственное значение из 1,…,m, отличное от j
(k1), j
(k2),…, jm(km-1).
, b2 = 
, b3 = 
, b4 = 
.
эквивалентны, если у них соответственно совпадают элементы, лежащие ниже главной диагонали.
.
раз. Определить временную вычислительную сложность алгоритма. Какова его емкостная вычислительная сложность?
и b = 
. Доказать, что тогда (x1,...,xn) < (y1,...,yn).
, n>1, то In=1, i1+1, 1, i2+1, 1, ..., i