Program gen (input, output);

End

end;

Из текста процедуры видно, что элемент 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 перестановки генерируются в следующем порядке:

1. <1 2 3 4> 7. <4 2 1 3> 13. <1 3 4 2> 19.< 4 3 2 1>

2. <2 1 3 4> 8. <2 4 1 3> 14. <3 1 4 2> 20. <3 4 2 1>

3. <3 1 2 4> 9. <1 4 2 3> 15. <4 1 3 2> 21. <2 4 3 1>

4. <1 3 2 4> 10. <4 1 2 3> 16. <1 4 3 2> 22. <4 2 3 1>

5. <2 3 1 4> 11. <2 1 4 3> 17. <3 4 1 2> 23. <3 2 4 1>

6. <3 2 1 4> 12. <1 2 4 3> 18. <4 3 1 2> 24. <2 3 4 1>

Упражнение. Исходя из матрицы 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=4.

1. <1 2 3 4> 7. <1 3 4 2> 13. <4 3 2 1> 19.< 2 4 3 1>

2. <1 2 4 3> 8. <1 3 2 4> 14. <3 4 2 1> 20. <4 2 3 1>

3. <1 4 2 3> 9. <3 1 2 4> 15. <3 2 4 1> 21. <4 2 1 3>

4. <4 1 2 3> 10. <3 1 4 2> 16. <3 2 1 4> 22. <2 4 1 3>

5. <4 1 3 2> 11. <3 4 1 2> 17. <2 3 1 4> 23. <2 1 4 3>

6. <1 4 3 2> 12. <4 3 1 2> 18. <2 3 4 1> 24. <2 1 3 4>.

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

const n= ; n1= ; {n1=n+1}

var p:array [0..n1] of 1..n1;

{p[1],...,p[n] - генерируемая перестановка}

r:array [1..n] of 1..n;

{r - перестановка, обратная к p[1],...,p[n] }

d:array [1..n] of -1..1; {d - вектор направлений}

i,j,k,t: integer;

begin

for i:=1 to n do

begin p[i]:=i; r[i]:=i; d[i]:=-1 end;

d[1]:=0; p[0]:=n1; p[n1]:=n1; i:=n;

while i<>1 do