C ECD EDC
Загальна кількість pазмещения - з N елементів по M може бути
знайдено за формулою:
N! /(N-M)! br/>
Нижче наводиться програма, яка вводить з клавіатури числа N, M і генерує всі можливі розміщення з N літер за M.
const
alphabet: string [26] = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ';
type
barray = array [1 .. 100] of byte;
var
b: barray;
N, M, i, j, k: byte;
z: longint;
Procedure WriteB (B: barray);
begin
Inc (Z); Write (Z: 3, ':');
for i: = 1 to M do write (alphabet [b [i]]);
writeln;
end;
Procedure SwapB (var B: barray; i, k: byte);
var x: byte;
begin
x: = B [i]; B [i]: = B [k]; B [k]: = x;
end;
Procedure PermuteAll (B: barray; N: byte);
var i, k, j: byte;
begin
WriteB (B);
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 (B, i, k);
for j: = i +1 to (i + ((N +1- i) div 2)) do SwapB (B, j, N + i +1- j);
WriteB (B);
end;
end;
begin
readln (N, M);
for i: = 1 to M do b [i]: = i;
PermuteAll (B, M);
while (true) do
begin
i: = M;
while (i> 0) and (b [i] = N-m + i) do Dec (i);
if i = 0 then exit;
Inc (B [i]);
for j: = i +1 to M do B [j]: = B [j-1] +1;
PermuteAll (B, M);
end;
readln;
end.
Пояснення до програми:
1. Головна програма вводить числа N, M і генерує за описаним вище алгоритму всі поєднання з N по M. Для кожного побудованого у векторі B поєднання викликається процедура PermuteAll, якій в якості параметрів передаються поточне поєднання B і кількість елементів у ньому M. Процедура PermuteAll генерує для отриманого поєднання всі можливі перестановки. p> 2. Масив B передається в процедуру PermuteAll за значенням (При оголошенні процедури при параметрі B немає ключового слова VAR) і тому зміни масиву B у процедурі PermuteAll не впливають на вміст масиву B у головній програмі.
3. У той же час для того, що б процедура SwapB могла обмінювати значення в B і повертати змінений масив в зухвалу її процедуру PermuteAll, масив B доданий в параметри процедури SwapB з передачею за адресою - використовуючи ключове слово VAR.
4. Для передачі масиву як параметр заведений спеціальний тип BARRAY.
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;
Procedure WriteB;
begin
for i: = 1 to N do write (alphabet [b [i]]);
writeln;
end;
begin
readln (K);
N: = 0;
for i: = 1 to K do
begin read (NN [i]); N: = N + NN [i]; end;
i: = 0;
for j: = 1 to k do
for m: = 1 to NN [j]
do begin Inc (i); B [i]: = j; end;
WriteB;
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;...
