АЛГОРИТМ ПЕРЕСТАНОВОК ПО СХЕМЕ «ЗИГЗАГ»
, Ю.
E-mail: a. *****@***com, hitev@ru
Санкт-Петербургский государственный университет
Предлагается алгоритм формирования перестановок, отличающийся более высоким быстродействием от известных алгоритмов [1]. В нём существенно сокращается количество пересылочных операций при обращении к процедуре генерирования перестановок по схеме «Зигзаг». Это достигается за счёт удвоения массива для хранения элементов формируемых перестановок, получения каждой новой перестановки путём переноса последнего элемента с одного края перестановки на другой и использования принципа зеркальности, заключающегося в том, что из всей последовательности n! перестановок достаточно получить её первую половину, а вторая половина является зеркальным отображением первой. Работа алгоритма формирования перестановок поясняется следующей таблицей.
№ | Формируемая перестановка | Зеркальная перестановка | ||||||||||||||
1 | 1 | 2 | 3 | 4 |
|
|
|
|
|
|
|
| 4 | 3 | 2 | 1 |
2 |
| 2 | 3 | 4 | 1 |
|
|
|
|
|
| 1 | 4 | 3 | 2 |
|
3 |
|
| 3 | 4 | 1 | 2 |
|
|
|
| 2 | 1 | 4 | 3 |
|
|
4 |
|
|
| 4 | 1 | 2 | 3 |
|
| 3 | 2 | 1 | 4 |
|
|
|
5 |
|
|
| 1 | 4 | 2 | 3 |
|
| 3 | 2 | 4 | 1 |
|
|
|
6 |
|
| 3 | 1 | 4 | 2 |
|
|
|
| 2 | 4 | 1 | 3 |
|
|
7 |
| 2 | 3 | 1 | 4 |
|
|
|
|
|
| 4 | 1 | 3 | 2 |
|
8 | 4 | 2 | 3 | 1 |
|
|
|
|
|
|
|
| 1 | 3 | 2 | 4 |
9 | 4 | 2 | 1 | 3 |
|
|
|
|
|
|
|
| 3 | 1 | 2 | 4 |
10 |
| 2 | 1 | 3 | 4 |
|
|
|
|
|
| 4 | 3 | 1 | 2 |
|
11 |
|
| 1 | 3 | 4 | 2 |
|
|
|
| 2 | 4 | 3 | 1 |
|
|
12 |
|
|
| 3 | 4 | 2 | 1 |
|
| 1 | 2 | 4 | 3 |
|
|
|
Формальное изложение процедуры генерирования перестановок на основе алгоритма по схеме «Зигзаг» приводится ниже.
Вход.
Если q = 0, то перейти к метке М1.
Вычислить: q = 0; т = п + n; h = 1; рi = i, si = n – i, i = 1, ···, n.
Перейти на Выход.
М1. Вычислить: k = 1.
M2. Если sk 
0, то перейти к метке М3.
Вычислить: sk = п – k; k = k + 1. Возвратиться к метке M2.
М3. Если k = п – 1, то вычислить: q = 1. Если k 1, то перейти к метке М4.
Если h = 1, то вычислить: i = sk; pm-i = pn-i.
Если h = –1, то вычислить: i = sk; pi = pn+i.
Вычислить: sk = sk –1. Перейти на Выход.
М4. Если h = 1, то вычислить: l = n + k – 1; j = l – 1.
Если h = – 1, то вычислить: l = n – k + 1; j = l + 1.
Вычислить: i = pj; pj = pl; pl = i; sk = sk – 1; h = – h.
Выход.
В рассмотренной процедуре приняты следующие обозначения:
q – указатель признака начального, q = 1, или последующих, q = 0, обращений к процедуре формирования перестановок;
п – длина перестановки (количество составляющих её элементов);
m – удвоенная длина перестановки;
h – указатель направления осуществляемых пересылок элементов;
рi – элемент перестановки, i = 1, ···, n;
si – указатель адресов пересылаемых элементов, i = 1, ···, n;
i, j, k, l – индексные или рабочие переменные.
Литература
1. Искусство программирования для ЭВМ. Основные алгоритмы. – М.: Мир, 1976. – 736 с.
Комбинаторные алгоритмы. Теория и практика. – М.: Мир, 1980. – 478 с.
