По вопросам приобретения обращаться

• Название: По вопросам приобретения обращаться
• Дата: 06.12.2019
• Размер: 5.46 Mb.
• Имя файла: Programmirovanie_v_algoritmakh.pdf
• Тип: Документы; #98984
• страница: 3 из 26

Вторая и третья задачи. Необходимо перечислить или сгенерировать все перестановки для заданного значения N, что требует введения отношения порядка на множестве перестано- вок. Только в этом случае задача имеет смысл. Предполагаем,
что перестановка хранится в массиве Р длины
Лексикогра- фический порядок на множестве всех перестановок определяет- ся следующим образом.
тогда и только тогда, когда су- ществует такое t>=1, что и
для всех i
При решении данной задачи решается и задача получения сле- дующей в лексикографическом порядке перестановки. Анти- лексикографический порядок на множестве всех перестановок определяется следующим образом.
тогда и только тогда,
когда существует такое t= что и
для всех i>t.
Пример (N=3).
Лексикографический (А)
132
Антилексикографический (В)
123 213

2. Комбинаторные алгоритмы
33
Лексикографический (А)
213 231 312 321
Антилексикографический (В)
132 312 231 321
Пример (N=4). Столбцы, обозначенные буквой А, означают генерацию перестановок в лексикографическом порядке, бук- вой В — антилексикографическом.
А
1234 1243 1324 1342 1423 1432
В
1234 2134 1324 3124 3214
А
2134 2143 2314 2341 2413 2431
В
1243 2143 1423 4123 2413 4213
А
3124 3142 3214 3241 3412 3421
В
1342 3142 1432 4132 3412 4312
А
4123 4132 4213 4231 4312 4321
В
2341 3241 2431 4231 3421 4321
Пример. Перестановка 11, 8, 5, 1, 7, 4, 10, 9, 6, 3, 2. Какая следующая перестановка идет в лексикографическом порядке?
Находим «скачок» — 4 меньше 10. Затем «в хвосте» пере- становки находим первый элемент с конца перестановки, боль- ший значения 4, на рисунке это значение 6. Меняем местами элементы 4 и 6 и «хвост» перестановки ухудшаем максималь- но, т. е. расставляем элементы в порядке возрастания. Проце- дура получения следующей в лексикографическом порядке пе- рестановки имеет вид:

34 2. Комбинаторные алгоритмы
Procedure GetNext;
Var
Begin {*Для перестановки N, N-1,...,1 процедура
не
*}
i : =N;
While (i>l) And (P [i]
"скачок".*}
While
Do Dec(j);
первый
элемент, больший значения P[i-1].*}
P[j]) ;
For
To
Div 2 - 1 Do Swap (P[i+j] ,
; {*Переставляем элементы
перестановки в порядке
End;
Procedure Swap (Var
Var
Begin
b:=t;
End;
Фрагмент общей схемы генерации:
в массиве Р - первая
в массиве Last -
перестановки.*}
While
Do
Eq
определяет равенство текущей перестановки
и последней; если не равны, то генерируется
следующая *}
GetNext;
Print;
End;
Изменим задачу. Необходимо перечислить все перестановки чисел от 1 до N так, чтобы каждая следующая перестановка по- лучалась из предыдущей с помощью транспозиции двух сосед- них элементов.
Например:
Возьмем перестановку p
1
..., и сопоставим с ней следу- ющую последовательность целых неотрицательных чисел
...,
Для любого i от 1 до N найдем номер позиции s, в кото- рой стоит значение i в перестановке, т. е. такое s, что и
подсчитаем количество чисел, меньших i среди р
1
,
...,
это количество и будет значением y
i
.

2. Комбинаторные алгоритмы
35
Пример:
i
t i
y i
1 11 0
2 8
1 3
5 1
4 1
1 5
7 0
6 4
3 7
10 2
8 9
0 9
6 5
10 3
5 11 2
0
Очевидно, что 0=
i
. Всего таких последовательностей N!,
т. е. множества перестановок и последовательностей чисел сов- падают по мощности. Построение последовательности чисел из перестановки очевидно, как и то, что разным перестановкам со- ответствуют разные последовательности чисел. Эта таблица на- зывается таблицей инверсий. Пару такую, что i и называют инверсией перестановки. Каждая инверсия как бы нарушает порядок в перестановке, единственная перестановка,
не имеющая инверсий, — это (1, 2, 3, ..., N). М. Холл устано- вил, что таблица инверсий единственным образом определяет соответствующую перестановку — обратное построение.
Пример. Последовательность
Четверка записана на втором месте, ибо только одна цифра в перестановке «стоит»
левее ее; имеем *4**. Тройка с учетом занятого места находит- ся на третьем месте — *43*. Двойке с учетом занятых мест при- надлежит четвертое место, т. е. получаем перестановку 1432.
Еще примеры. Дана последовательность чисел 0023. Четверка стоит на четвертом месте (3+1), тройка находится на третьем месте (2+1) — **34, двойка (0+1) — на первом месте — получа- ем 2134. Еще одна последовательность — 0112. Четверка на третьем месте (2+1), тройка на втором (1+1), двойка на втором
(1+1), но с учетом занятых мест на четвертом получаем пере- становку 1342. Идею осознали?
Таблица последовательностей чисел и соответствующих пе- рестановок для N-4.
0000 0001 0002 0003 0013 0012 4321 3421 3241 3214 2314 2341 0010 0020 0021 0022 0023 2431 4231 4213 2413 2143 2134 0123 0122 0121 0120 0110 0111 1234 1243 1423 4123 4132 1432 0112 0113 0103 0102 0101 0100 1342 1324 3124 3142 3412 4312
Зрительный образ предлагаемой схемы генерации. Пусть есть доска в форме лестницы. Высота i вертикали равна i. В
первоначальном состоянии шашки стоят на первой горизонта- ли. Стрелки указывают направление движения шашек (вверх).

36 2. Комбинаторные алгоритмы
За один ход можно передвинуть одну шашку в направлении стрелки. Если шашку передвинуть нельзя, то осуществляется переход к следующей слева шашке. После того как найдена шашка, которую можно передвинуть помимо передвижения шашки, осуществляется смена направления движения всех ша- шек справа от найденной. Ниже на рисунке приведена смена состояний шашек на доске при N=4, начиная с последователь- ности чисел 0023. Под последовательностями чисел записаны соответствующие им перестановки.
0023 2134 0123 1234 0122 1243 0121 1423
Оказывается, что изменение на единицу одного из элементов последовательности соответствует транспозиции двух соседних элементов перестановки. Увеличение y[i] на единицу соответст- вует транспозиции числа i с правым соседом, уменьшение — с левым соседом. Итак, помимо генерации последовательностей необходимо уметь находить число i в перестановке и менять его местами с одним из «соседей», но это уже чисто техническая задача.
Опишем используемые данные.
Var
Of 0 .
Of
{*Хранение
последовательности чисел.*}
{*Направление
движения "шашек". *}
Процедура формирования начальной перестановки и нача- льных значений в массивах Y и D.
Procedure First;
Var
Begin
For i : = 1 To N Do Begin
D[i]:=1;
End;
End;

2. Комбинаторные алгоритмы 37
Поиск номера «шашки», которую можно передвинуть. При и
или D[i]=-l и Y[i]=0 шашку с номером i нель- зя передвинуть.
Function
{*Если значение функции равно
то нет ни одной шашки, которую можно
Var
Begin
i:=N;
While (i>1) And (((D[i]=1) And
Or
And (Y[i]=0)))
=i ;
End;
Основная логика генерации перестановок имеет вид:
Begin
First;
While
Do Begin
Solve
;
pp Then Print;
End;
End;
Уточним процедуру генерации следующей перестановки.
Procedure
q:Boolean);
Var
Begin
q:=(i>l);
номер
которую
можно
*}
If i>1 Then Begin
{*Передвигаем шашку - изменяем
последовательность чисел.*}
For
N Do
{*Изменяем
направление движения шашек, находящихся
справа от
позицию в
в которой записано число
{*Определяем соседний элемент
перестановки для выполнения
P[dj]);
End;
End;

38 2. Комбинаторные алгоритмы
Остался последний фрагмент логики, требующий уточне- ния, — поиск в перестановке позиции, в которой находится элемент i. Он достаточно прост.
Function
(i : Integer): Integer;
Var
Begin
While (j>0) And (P[j]<>i) Do Dec(j);
Who_i
End;
Четвертая задача. Как номеру определить перестановку относительно того порядка, разумеется, который введен на мно- жестве перестановок? Остановимся на лексикографическом по- рядке. Рассмотрим идею решения на примере. Пусть N равно 8 и дан номер L, равный 37021. Найдем соответствующую переста- новку. Пусть на месте записана единица. Таких переста- новок 7!, или 5040
При 2 тоже 5040 (2*******). Итак,
37021 Div 5040=7. Следовательно, первая цифра в перестановке
8. Новое значение L (37021 Mod 5040=1741) 1741. Продолжим рассуждения. Оформим, как обычно, их в виде таблицы.
Обратим внимание на третью строку, в которой на третье место записывается цифра 4. То, что записываются не цифры 1
и 2, очевидно: их требуется пропустить. Цифра три «занята»,
поэтому записываем 4. Точно так же в строках 4, 5 и 7.
О программной реализации. Пусть таким образом,
значение L не превосходит максимального значения типа Lon-
gInt. Определим следующие константы.
Const
Of
6800,479001600) ;
N! для N от 0 до 12.*}

2. Комбинаторные алгоритмы
39
И процедура.
Procedure
Var
Set Of Byte;
Begin
для фиксации цифр,
задействованных в
For i : = 1
N Do Begin
Sc:=L Div
Mod
j:=1;
While (sc<>0) Or (j In Ws) Do Begin
If Not (j In Ws) Then Dec(sc);
(j) ;
End;
очередную цифру. *}
End;
End;
Для более глубокого понимания сути приведем часть трасси- ровки работы процедуры для ранее рассмотренного примера.
I
1 2
3 4
Sc
7 6
5 4
3 2
1 0
2 1
0 2
1 1
0 2
1 1
1 0
L
37021 1741 301 61 13
J
1 2
3 4
5 6
7 1
2 3
1 2
3 4
1 2
3 4
5
Ws
[]
[8]
[3,8]
[3,4,8]
[3,4,5,8]
P
********
8********
83******
834******
8345****

40 2. Комбинаторные алгоритмы
Пятая задача. По перестановке получить ее номер, не вы- полняя генерацию множества перестановок. Начнем с примера.
Пусть N равно 8 и дана перестановка 53871462. Схема:
7!*<количество цифр в перестановке на 1-м месте, идущих до цифры 5, с учетом занятых цифр — ответ 4>
6!*< количество цифр в перестановке на 2-м месте, идущих до цифры 3, с учетом занятых цифр — ответ 2>
5!*< количество цифр в перестановке на 3-м месте, идущих до цифры 8, с учетом занятых цифр — ответ 5>
4!*< количество цифр в перестановке на 4-м месте, идущих до цифры 7, с учетом занятых цифр — ответ 4>
3!*< количество цифр в перестановке на 5-м месте, идущих до цифры 1, с учетом занятых цифр — ответ 0>
2!*< количество цифр в перестановке на 6-м месте, идущих до цифры 4, с учетом занятых цифр — ответ 1>
количество цифр в перестановке на 7-м месте, идущих до цифры 6, с учетом занятых цифр — ответ 1>
Итак,
24+0*6+1*2+1*1=22305.
Function
Var
Of Byte;
Begin
{*Множество цифр перестановки.*}
For i : = 1
N Do Begin
количество цифр.*}
While j
If Not (j In
Then
(sq);
(j);
End;
{*Цифра P[i] задействована.*}
число
перестановок на значение текущей цифры.*}
End;
End;
2.2.2. Размещения
Первая задача. Подсчитать количество размещений для не- больших значений N и М можно с помощью следующих про- стых функций.

2. Комбинаторные алгоритмы
41
Function
LongInt;
Var i,z: LongInt;
Begin
=1
For i:=0 To
Do z :=z* (n-i);
End;
Рекурсивный вариант реализации.
Function Plac (n,m:LongInt):
Begin
If
Then
Else
End;
Функции дают правильный результат при N=<12. Для боль- ших значений N необходимо использовать «длинную» арифме- тику.
Вторая задача. Требуется сгенерировать все размещения для заданных значений N и М в лексикографическом порядке.
Пример. N=4,
В таблице приведены размещения в лексикографическом порядке.
123 124 132 134 142 143 213 214 231 234 241 243 312 314 321 324 341 342 412 413 421 423 431 432
Текст решения имеет вид:
Program
Const n=4;
взяты в качестве
Var
Of
{*Массив для
хранения элементов
S:Set Of Byte;
хранения использованных
в размещении цифр.*}
Procedure
{*Параметр t
определяет номер позиции в
Var i:Byte;
Begin
For i:=1 To n Do
цифры и находим
1-ю
If Not (i In S) Then Begin

42 2. Комбинаторные алгоритмы
её в множестве занятых
цифр.*}
A[t]
{*Записываем её в
If
Then Solve
Else Print; {*Если
размещение не
то идем
к следующей позиции, иначе
выводим очередное
=S- [i]; {*Возвращаем цифру в число
End;
End;
Фрагмент основной программы.
Begin S: = []; Solve (1) ; End.
Для генерации размещений можно воспользоваться проце- дурой генерации перестановок из предыдущего пункта. Требу- ется только уметь «вырезать» из очередной перестановки пер- вые М позиций и исключать при этом повторяющиеся последовательности.
Третья задача. По заданному размещению найти следую- щее за ним в лексикографическом порядке.
Свободными элементами размещения назовем те элементы из множества от до N, которых нет в текущем размещении
(последовательности из М элементов). Пример. N=5,
и размещение
4. Свободными элементами являются 2 и 5.
Первый вариант решения заключается в том, чтобы дописать в размещение свободные элементы в убывающем порядке
4 5 2), сгенерировать следующую перестановку (1 3 5 2 4) и отсечь первые М элементов (1 3 5). Получаем следующее размещение.
Реализация этой же идеи, но без обращения к генерации следу- ющей перестановки приводится ниже по тексту.
Её суть:
• Начинаем просмотр размещения с последнего элемента и идем, если необходимо, до первого.
• Находим первый свободный элемент, который больше,
чем элемент в рассматриваемой позиции размещения.
• Если такой элемент найден, то заменяем им текущий, а в
«хвост» размещения записываем свободные элементы в порядке возрастания и заканчиваем работу.
• Если такого элемента не найдено, то переходим к следую- щей
Const
Var
.
Of Byte;

2. Комбинаторные алгоритмы 43
Procedure GetNext;
Var
Of
{*Массив для
хранения признаков занятости элементов
в размещении.*}
Function
{*Функция поиска
первого не занятого
Begin
While (t<=n) And Not (Free [t]) Do Inc(t);
первый свободный элемент.*}
If t>n Then
{*Если такого элемента
нет, то значение функции равно нулю.*}
Else
Номер первого свободного
End;
Begin
For i:=1
n Do Free
{*Массив
свободных
For
Do Free
{*По
размещению исключаем занятые элементы.*}
{*Начинаем с конца размещения.
Предполагаем, что анализируемое
размещение не является последним.*}
While (i>0) And
Do Begin
не
позицию в размещении,
элемент в которой допускается
выполняем действия из
При нашем
предположении такая позиция обязательно
элемент,
записанный в позиции i.*}
Dec(i); {*Переходим к следующей позиции.*}
End;
{*Переводим текущий элемент
в найденной позиции в
{*Находим свободный
элемент, больший
{*Считаем его
A[i]:=q;
его в
к:=1; {*Формируем "хвост"
For j:=i+1
Do
{*Co следующей позиции
до конца
While (k<=n) And
Dо {*Пока не
найдем первый свободный

44
2. Комбинаторные алгоритмы
If
Then
Else
найденный элемент
в
{*Считаем его занятым.*}
End;
End;
Четвертая задача. При заданных значениях N М по но- меру размещения L определить соответствующее размещение
(упорядочены в лексикографическом порядке).
Рассмотрим размещения из 5 по 3 элемента, их 60. В табли- це часть размещений, вместе с их номерами, приводится в лек- сикографическом порядке. Первому размещению соответствует номер 0.
0 1
3 4
5 123 125 132 134 135 7
8 9
10 11 142 143 152 153 154 12 13 14 15 16 17 213 214 215 231 234 235 18 19 20 21 22 23 241 243 245 251 253 254 24 25 26 27 28 29 312 314 315 321 324 325 30 31 32 33 34 341 342 345 351 352
Значение (в общем случае ) равно 12. Количество размещений с фиксированным значением в первой позиции равно 12, а это уже путь к решению. Пусть нам задан номер 32
и массив свободных элементов
3 4 5 (номера элементов мас- сива считаются с 0). Вычисляя 32 Div 12, получаем 2, следова- тельно, в первой позиции записана цифра, стоящая на 2-м мес- те в массиве свободных элементов, а это цифра 3. Оставшееся количество номеров 32 Mod 12 =8, массив свободных элементов
4 5. Продолжим процесс вычисления - 8 Div 3=2 ,
следующая цифра 4. Оставшееся количество номеров 8 Mod 3
=2, массив свободных номеров
5. Продолжим - 2 Div 1 =2,
что соответствует цифре 5.
Const n=5;
Var
Of Integer;
Procedure
{*B процедуре
использована функция
- вычисления
количества размещений.*}
Var
Of
свободных
элементов

2. Комбинаторные алгоритмы 45
Begin
For i:=1
n Do Free
;
For i : = 1
Do Begin
- номер позиции
в размещении.*}
{*Количество размещений,
приходящихся на один фиксированный
элемент в позиции
q:=L Div
{ *Вычисляем номер свободного
элемента
{*Формируем элемент
For j : = q + 1
n-i Do Free
найденный элемент
размещения исключаем из
Mod t; {*Изменяем значение номера
размещения (переход к меньшей
размерности).*}
End;
End;