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

while (true) do

begin

i:=N;

while (i>0) and (B[i]>=B[i+1]) do i:=i-1;

if i=0 then exit;

for j:=i+1 to N do

if (B[j]>B[i]) then K:=j;

SwapB(i,k);

for j:=i+1 to (i+ ((N+1-i) div 2))

do SwapB(j,N+i+1-j);

writeB;

end;

end.

В программе введены 2 процедуры WriteB и SwapB.

Процедура WriteB вызывается всякий раз, когда построена очередная перестановка. В данной программе процедура WriteB просто выводит соответствующую последовательность латинских букв.

Процедура SwapB(i,k) введена для упрощения понимания главной программы. SwapB просто обменивает значениями два элемента массива B - те, которые имеют индексы, соответствующие значениям параметров процедуры i и k.

Процедура SwapB используется в тексте программы два раза

1) При обмене значениями двух найденных элементов с индексами I и K.

2) При обеспечении попарного обмена элементов "хвоста", в котором текущий элемент с индексом j обменивается местами со своим "партнером", находящимся на позиции N+i+1-j. Таким образом, I+1-ый элемент поменяется (при J=I+1) местами с N-м элементом, I+2-ой элемент (при J=I+2) с N-1-ым и т.д.

Общее число перестановок из N элементов равно N! (читается N факториал). Напомним, что N! = 1*2*3*...*N

3 Сочетания

Пусть имеем 5 компонент, обозначенных латинскими буквами A, B, C, D, E соответственно.

Тогда все сочетания из этих 5 компонент по 3, выписанные в лексикографическом порядке (для букв и цифр от 1 до 5) будут таковы:

ABC 123

ABD 124

ABE 125

ACD 134

ACE 135

ADE 145