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

5. Для подсчета всех сгенерированных размещений используется переменная Z в процедуре WriteB.

5 Перестановки с повторениями

Перестановки с повторениями допускают повторное использование элементов. Например, пусть имеем множество, состоящее из двух символов A и двух символов B.

Тогда все перестановки с повторениями из этих символов будут таковы:

AABB ABBA BABA ABAB BAAB BBAA

В общем случае, если имеем

N1 предметов 1-го вида

N2 предметов 2-го вида

...

Nk предметов K-го вида

Общее количество перестановок может быть вычислено по формуле

N!/ (N1!*N2!*..*Nk!)

Алгоритм аналогичен генерации перестановок без повторений за исключением формирования начальной перестановки:

i=0;

Для j от 1 до k

Для m от 1 до N[j] i=i+1; B[i]=j;

Ниже приводится программа генерации перестановок с возвращениями. Количество K различных типов предметов, обозначенных латинскими буквами вводится с клавиатуры. С клавиатуры также вводятся количества NN[j] предметов каждого типа.

Сумма введенных NN[j] определяет общее количество элементов в каждой из генерируемых перестановок.

const

alphabet : string[26] = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ';

var

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

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

NN : array [1..100] of longint;

Procedure SwapB(i,k:byte);

var x : byte;

begin

x:=B[i]; B[i]:=B[k]; B[k]:=x;

end;