= 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 відповідно. p> Тоді всі поєднання з цих 5 компонент по 3, виписані у лексикографічному порядку (для букв і цифр від 1 до 5) будуть такі:
ABC 123
ABD 124
ABE 125
ACD 134
ACE 135
ADE 145
BCD 234
BCE 235
BDE 245
CDE 345
Неформально алгоритм генерації послідовності чисел в лексикографічному порядку можна записати наступним чином. Виберемо найменші M з наявних N чисел і випишемо їх у порядку зростання - і випишемо їх у порядку зростання - 1 2 3 - це початкове поєднання. Очевидно, що найбільші M чисел з наявних (3 4 5), виписані у порядку зростання, складуть останнє поєднання.
Для того, що б з поточного поєднанню отримувати наступне, можна поступати таким чином:
Знаходимо позицію в поточному поєднанні, на якій не варто Останнім з можливих значень, і потім збільшуємо його на 1. А все наступні елементи поєднання отримуємо збільшенням на 1 попереднього елемента поєднання.
Наприклад нехай поточне поєднання
1 5 березня
Аналіз починаємо з останньої позиції поєднання.
5 - це останнє можливе значення, тому переходимо до попередньої позиції. 3 - це не останнє можливе значення для цієї позиції (Яким є 4 в даному випадку). Тому ми його збільшуємо на 1 - отримуємо 4. А число в такій позиції отримуємо додатком 1 до цієї 4-ці - і отримуємо 5. Таким чином таке значення буде 1 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;
begin
for i: = 1 to M do write (alphabet [b [i]]);
writeln;
end;
begin
readln (N, M);
for i: = 1 to M do b [i]: = i;
WriteB;
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;
WriteB;
end;
end.
Нагадаємо, що загальна кількість сполучень з N елементів по M може бути обчислено за формулою C (N, M) = N! /(M! * (N-M)!) br/>
4 Розміщення
Для генерації всіх розміщень з N елементів по M можна скористатися композицією алгоритмів, викладених вище. Тобто генерувати всі поєднання з N по M, а потім для кожного отриманого поєднання генерувати всі перестановки з M елементів.
Наприклад, при генерації всіх розміщень з 5 елементів по 3, у випадку, якщо самі елементи позначені латинськими літерами A, B, C, D, E потрібно отримати наступну послідовність, представлену для компактності у вигляді 10 рядків, кожна з яких представляє всі можливі поєднання з 3 літер першого елемента рядки. А самі перші елементи рядків якраз і являють всі можливі поєднання з 5 букв по 3.
ABC ACB BAC BCA CAB CBA
ABD ...
ABE ...
ACD ...
ACE ...
ADE ...
BCD ...
BCE ...
BDE ...
CDE CED DCE DE...
