p> alphabet: string [26] = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ';
var
b: array [1 .. 100] of byte;
N, i: byte;
begin
readln (N);
for i: = 1 to N +1 do b [i]: = 0;
writeln ('Порожнє безліч');
while (b [N +1] = 0) do
begin
i: = 1;
while B [i] = 1 do
begin B [i]: = 0; inc (i); end;
B [i]: = 1;
for i: = 1 to n do
if b [i] = 1 then write (alphabet [i]);
writeln;
end;
end.
При необхідності обробляти (аналізувати) побудовані підмножини можуть бути додані виклики процедур обробки, які отримують в якості параметра масив B (який вказує своїми одиничними елементами номери елементів безлічі, включених до поточне підмножина).
2 Перестановки
Нехай ми маємо 4 компоненти, позначені літерами A, B, C, D відповідно. p> Тоді безліч всіх перестановок з цих компонент буде включати наступні елементи:
ABCD BACD CABD DABC
ABDC BADC CADB DACB
ACBD BCAD CBAD DBAC
ACDB BCDA CBDA DBCA
ADBC ​​BDAC CDAB DCAB
ADCB BDCA CDBA DCBA
Проілюструємо спочатку алгоритм побудови наступній перестановки на прикладі перестановок з 9 компонент, позначених відповідно цифрами від 1 до 9.
Перша з таких перестановок це
1 2 3 4 5 6 7 8 9
Нехай поточна перестановка з 9 компонент:
1 9 5 8 4 7 6 3 2
Яким буде наступне значення перестановки, якщо ми будуємо її в лексикографічному порядку (тобто в порядку зростання величини числа, складеного з цих цифр)?
Правильна відповідь такий:
1 9 5 8 6 2 3 4 7
Як він виходить?
Перш за все, необхідно переглядати вихідний масив від кінця до початку, що б знайти перше число, яке МЕНШЕ попереднього в нашому випадку - це 4
(7> 6> 3> 2, а 4 <7)
Далі серед переглянутих чисел праворуч від знайденої 4 ми шукаємо останнє число яке більше 4. Це число 6. p> (7> 4, 6> 4, 3 <4, 2 <4)
Потім міняємо ці 2 знайдених числа (4 і 6) місцями, отримуємо:
1 9 5 8 6 7 4 3 2
І тепер числа (праворуч від 6), які складають убуваючу послідовність (4 Липень 3 лютого), попарно міняємо місцями так, що б вони склали зростаючу послідовність (2 березня 7 квітня):
1 9 5 8 6 2 3 4 7
Це і є наступна перестановка.
А яка перестановка буде останньою для даного прикладу?
Сподіваюся, що вдумливий читач здогадався і сам:
9 8 7 6 5 4 3 2 1
Кілька неформально алгоритм побудови наступній перестановки за поточною може бути записаний таким чином:
1. Від кінця до початку перестановки шукаємо перший елемент B [i] такий, що B [i]
2. Від елемента I +1 до кінця шукаємо останній елемент, більший ніж B [i], запам'ятовуємо його індекс - K
3. Міняємо місцями ці елементи - з номерами I і K
4. Всю групу елементів від i +1- го елемента до N-го попарно міняємо місцями (i +1- ий елемент з N-им, i +2- ой елемент з N-1-им і т.д.)
Формалізовано алгоритм генерації всіх перестановок з N елементів може бути записаний таким чином:
Введення N
Прописуємо масив B послідовно числами від 1 до N
Це перша - початкова - перестановка, виводимо її
Поки (істина)
i = N
Поки (i> 0) і (B [i]> = B [i +1]), i = i-1
Якщо i = 0 то кінець роботи
Для j від i +1 до N
якщо B [j]> B [i] то K = j
Обмін значень B [i] і B [k]
Для j від i +1 до (i + ((N +1- i) div 2))
Обмін значень B [j] і B [N + i +1- j]
Висновок поточної перестановки B
Зрозуміло, що цикл попарних перестановок "Хвоста" масиву B не можна робити від i +1 до N-го елемента - інакше елементи поміняються місцями по 2 рази - і вийти, що нічого не змінилося. Цикл потрібно виконати для половини цього "хвоста". Цьому і служить кілька складне для розуміння значення кінцевої змінної циклу: i + (N +1- i) div 2
Нижче наводиться програма, генеруюча всі перестановки з N компонент, позначених N першими літерами латинського алфавіту. p> const
alphabet: string [26] = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ';
var
b: array [1 .. 100] of byte;
N, i, j, k: byte;
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 (N);
for i: = 1 to N do b [i]: = i;
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: ...
