Лекция 23. Алгоритмы перебора множеств (Электронные лекции)

Лекции по курсу “Алгоритмы и алгоритмические языки”, 1 курс, 1 поток, 2010/2011 уч.год.Лекция 23 Алгоритмы перебора множеств23.1. Постановка задачи.23.1.1. Перестановка некоторого набора элементов – это упорядоченная последовательность из этихэлементов.

Например, множество {1, 2, 3} имеет 6 различных перестановок (1, 2, 3), (1, 3, 2),(2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)23.1.2. Для любого множества из n элементов существует ровно n! = 1⋅2⋅...⋅n различныхперестановок.В самом деле, пусть Р(n) – число перестановок n-элементного множества (дляопределённости рассмотрим множество M = {1, 2, ..., n}). На первом месте в перестановкеможет стоять одно из чисел 1, ..., n. Перестановок множества M, в которых на первом местестоит число i ровно столько, сколько есть различных перестановок оставшихся n - 1 чисел,то есть Р(n – 1). Поэтому, Р(n) = n⋅Р(n – 1). По индукции получаем Р(n) = 1⋅2⋅...⋅n = n!23.1.3. Для справок: таблица n! n⋅n! и 4⋅n⋅n! для 10 ≤ n ≤ 14.nn!n⋅n!103,628,80036,288,0001139,916,800439,117,80012479,001,6005,748,019,200136,227,020,80080,951,270,4001487,178,291,2001,220,496,076,800256 Gbyte= 274,877,906,944 Byte4⋅n⋅n!145,152,0001,758,471,20022,992,076,800323,805,081,6004,881,984,307,200Одна перестановка из n элементов занимает n байтов (если 0 ≤ n ≤ 255), а все перестановкизанимают n⋅n! байтов.

Из таблицы видно, что при n = 14 все перестановки из n элементов непоместятся на жестком диске (винчестере) емкостью 256 Gbyte.23.1.4. Задача состоит в том, чтобы написать программу, которая выводит все перестановкимножества {1,2,..., n} в лексикографическом порядке (перестановки можно рассматриватькак слова в алфавите B = {1, 2, ..., n})23.2. Рекурсивный алгоритм генерации перестановок.23.2.1. Алгоритм. Будем перебирать перестановки чисел {1, 2, ..., n} в глобальном массиве a[n],последовательно заполняя его числами 1, ..., n в различном порядке. Для перебора всехперестановок применим ту же рекурсивную идею, что и при доказательстве формулычисла перестановок: будем записывать на первое место в массиве a по очереди числа 1, ..., n,и для каждого числа рекурсивно вызывать функцию генерации перестановок оставшихсяn – 1 чисел.23.2.2.

Си-программа.#include <stdio.h>#include <stdlib.h>1(с) Кафедра системного программирования ф-та ВМК МГУ, 2010Лекции по курсу “Алгоритмы и алгоритмические языки”, 1 курс, 1 поток, 2010/2011 уч.год.void PrintPerm(int *a, int n) {int i;for(i = 0; i < n; i++) {printf("%3d", a[i]);}printf("\n");}void GenPerm(int *a, int *b, int i, int n) {if(i == n) {PrintPerm(a, n);}else {int j;for(j = 0; j < n; j++) {if(b[j] == 0) {b[j] = 1;a[i] = j + 1;GenPerm(a, b, i+1, n);b[j] = 0;}}}}int main() {int *a, *b;int n;scanf("%d", &n);a = (int*)malloc(n*sizeof(int));b = (int*)malloc(n*sizeof(int));GenPerm(a, b, 0, n); /* первый вызов генератора */free(a);free(b);return 0;}23.2.3.

Отметим, что рассмотренный рекурсивный алгоритм, который очень прост в реализации,достаточно эффективен (в соответствии с определением 23.3)23.3. Определение. Переборный алгоритм называется эффективным, если он работает время,которое растёт пропорционально суммарному размеру перебираемых им элементов, то естьпроизведению числа элементов на размер описания одного элемента.В случае перестановок объектов типа char каждая перестановка занимает n байт, так чтопроизведение числа элементов на размер описания одного элемента равно n⋅n!2(с) Кафедра системного программирования ф-та ВМК МГУ, 2010Лекции по курсу “Алгоритмы и алгоритмические языки”, 1 курс, 1 поток, 2010/2011 уч.год.В случае перестановок объектов типа int каждая перестановка занимает 4⋅n байт, так чтопроизведение числа элементов на размер описания одного элемента равно 4⋅n⋅n!23.4.

Нерекурсивный алгоритм. Задачу посещения (перебора) всех перестановок заданногомножества можно свести к следующей задаче: по данной перестановке сгенерироватьследующую за ней перестановку (например, в лексикографическом порядке). Один из первыхалгоритмов решения этой задачи придумал индийский математик Пандит Нарайана еще в XIVвеке (он изучал свойства магических квадратов).23.4.1. Алгоритм Нарайаны (генерация лексикографически следующей перестановки).Алгоритм Нарайаны по любой данной перестановке из n элементов а1 а2 ...

аnгенерирует следующую (в лексикографическом порядке) перестановку.Если алгоритм Нарайаны применить в цикле к исходной последовательности nэлементов а1 а2 ... аn, отсортированных так, что а1 ≤ а2 ≤ ... ≤ аn, то он сгенерирует всеперестановки элементов множества {а1 а2 ... аn}, в лексикографическом порядке.(Например, исходя из перестановки {1,2,2,3}, сгенерирует остальные перестановки вследующем порядке: 1223, 1232, 1322, 2123, 2132, 2213, 2231, 2312, 2321, 3122, 3212,3221).23.4.2. Сначала рассмотрим пример.

Пусть n = 5 и пусть элементами множества являютсячисла 1, 2, 3, 4 и 5. Рассмотрим перестановку 324 15; лексикографически следующимибудут: 32451, 32514, 32541, 34125, …23.4.3. Алгоритм Нарайаны.Шаг 1. [Первая перестановка.] Составить перестановку а1 а2 ... аn (а1 < а2 < ... < аn).Шаг 2. [Найти j, для которого аj < аj+1] Установить j ← n – 1. Если аj ≥ аj+1, уменьшать jна 1 повторно, пока не выполнится условие аj < аj+1.

Если окажется, что j = 0,завершить алгоритм. (На шаге 2 j является наименьшим индексом, для которогобыли посещены все перестановки, начиная с а1 ... аj. Следовательно,лексикографически следующая перестановка увеличит значение аj).Шаг 3. [Увеличить аj] Установить l ← n.

Если аj ≥ аl, уменьшать l на 1 повторно, покане выполняется условие аj < аl. Затем поменять местами аj ↔ аl.Пояснение. Поскольку аj+1 ≥ ... ≥ аn, элемент аl является наименьшимэлементом, который больше аj, и который может следовать за а1 ... аj-1 вперестановке.Передзаменойвыполнялисьотношенияa j + 1 ≥ ... ≥ al − 1 ≥ al ≥ a j ≥ al + 1 ≥ ...

≥ an , а после замены – выполняются отношенияa j + 1 ≥ ... ≥ al − 1 ≥ a j ≥ al ≥ al + 1 ≥ ... ≥ anШаг 4. [Обратить аj+1 ... аn] Установить k ← j + 1 и l ← n. Затем, если k < l, поменятьместами аk ↔ аl, установить k ← k + 1, l ← l – 1 и повторять, пока невыполнится условие k ≥ l. Вернуться к шагу 1.23.4.4. Программа на языке Си.#include <stdio.h>#include <stdlib.h>int NextPerm(int *a, int n) {/* массив *a содержит одну из перестановок n чисел */3(с) Кафедра системного программирования ф-та ВМК МГУ, 2010Лекции по курсу “Алгоритмы и алгоритмические языки”, 1 курс, 1 поток, 2010/2011 уч.год.int i, k, t, tmp;/* находим k такое что: а[k] < а[k + 1] > ....

> а[n - 1]*/for(k = n – 2; (а[k] > a[k + 1]) && (k >= 0); k--);if(k == -1) return 0; /* последняя перестановка *//* находим t > k такое, что среди а[k + 1],..., а[n – 1]*//* a[t] – минимальное число, большее а[k] */for(t = n - 1; (a[k] > a[t]) && (t >= k + 1); t--);tmp = a[k];a[k] = a[t];a[t] = tmp;/* участок массива a[k + 1],..., a[n – 1] записываем в *//* обратном порядке */for(i = k + 1; i <= (n + k)/2; i++) {t = n + k – i;tmp = a[i];a[i] = a[t];a[t] = tmp;}return i;}void PrintPerm(int *a, int n) {int i;for(i = 0; i < n; i++) {printf("%3d", a[i]);}printf("\n");}int main() {int *a, n, i;scanf("%d", &n);a = (int*)malloc(n*sizeof(int));/* a ← {l, 2, ..., n} */for(i = 0; i < n; i++) a[i] = i + 1;do {PrintPerm(a, n); }while (NextPerm(a, n));return 0;}4(с) Кафедра системного программирования ф-та ВМК МГУ, 2010.