Реферат: Генерация комбинаторных объектов

BCE 235

BDE 245

CDE 345

Неформально алгоритм генерации последовательности чисел в лексикографическом порядке можно записать следующим образом. Выберем наименьшие M из имеющихся N чисел и выпишем их в порядке возрастания - и выпишем их в порядке возрастания - 1 2 3 - это начальное сочетание. Очевидно, что наибольшие M чисел из имеющихся (3 4 5), выписанные в порядке возрастания, составят последнее сочетание.

Для того, что бы по текущему сочетанию получать следующее, можно поступать следующим образом:

Находим позицию в текущем сочетании, на которой не стоит последнее из возможных значений, и затем увеличиваем его на 1. А все последующие элементы сочетания получаем увеличением на 1 предыдущего элемента сочетания.

Например пусть текущее сочетание

1 3 5

Анализ начинаем с последней позиции сочетания.

5 - это последнее возможное значение, потому переходим к предыдущей позиции. 3 - это не последнее возможное значение для этой позиции (каковым является 4 в данном случае). Потому мы его увеличиваем на 1 - получаем 4. А число в следующей позиции получаем прибавлением 1 к этой 4-ке - и получаем 5. Таким образом следующее значение будет 1 4 5

Более формализовано этот алгоритм может быть записан следующим образом:

Ввод N, M (из сколька, по сколько)

Заносим в массив B числа от 1 до M

Это первое сочетание, выводим его

Пока (истина)

i=M

Пока (i>0) и (b[i]=N-m+i), i=i-1

Если i=0 то работа завершена

B[i]=B[i]+1

Для j от i+1 до M B[j]=B[j-1]+1;

Вывод B - следующей перестановки

Ниже приводится программа, которая считывает с клавиатуры значения N и M и выводит в лексикографическом порядке все сочетания из N первых латинских букв по M.

uses crt;

const

alphabet : string[26] = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ';

var

b : array [1..100] of byte;

N,M,i,j,k : byte;

Procedure WriteB;