друге, коли з точки зору умови задачі не має значення, скільки саме елементів повинно входити в шукане підмножина. На прикладі такого завдання ми і напишемо програму генерації всіх підмножин вихідного безлічі в лексикографічному порядку. Завдання взята з книги [5]. p> Умова . Дан цілочисельний масив a [1 .. N] (N ВЈ 20) і число M. Знайти підмножина елементів масиву a [i1], a [i2], ... a [ik] таке, що 1 ВЈ i1
Рішення . В якості рішення наведемо процедуру генерації всіх підмножин, які можна скласти з елементів масиву і функцію перевірки конкретного підмножини на відповідність умові задачі.
function check (j: longint): boolean;
var k: integer; s: longint;
begin
s : = 0;
for k : = 1 to n do
if (( j shr ( k -1)) and 1) = 1 {дане умова означає, що в
k -й справа позиції числа j , в 2-й системі, коштує 1}
then s: = s + a [k];
if s = m then
begin
for k: = 1 to n do
if ((j shr (k-1)) and 1) = 1 then write (a [k]: 4);
writeln
end
end;
procedure subsets (n: integer) ;
var q , j : longint ;
begin
q : = 1 shl n ; {таким чином ми поміщаємо в q число 2 ^ n }
for j : = +1 to q -1 do {цикл по всіх підмножини}
if check (j) then exit
end;
Зауважимо, що якщо всі елементи в масиві позитивні, то, змінивши порядок розгляду підмножин, рішення наведеної вище завдання можна зробити більш ефективним. Так, якщо сума елементів якого-небудь підмножини вже більше, ніж M , то розглядати підмножини, які включають їх у себе вже не має сенсу. Перерахунок ж сум можна оптимізувати, якщо кожне наступне сгенерированное підмножина буде відрізнятися від попереднього не більше, ніж на один елемент (Такий спосіб перерахування підмножин показаний в [2]). Наведена ж програма черезвичайно проста, але володіє одним недоліком: ми не можемо ні в якому випадку з її допомогою перебирати всі підмножини множин, що складаються з більш, ніж 30 елементів, що обумовлено максимальним числом бітів, що відводяться на подання цілих чисел у Турбо Паскалі (32 біта). Але, як уже було сказано вище, насправді, перебір всіх підмножин у множин більшої розмірності навряд чи можливий за час, відведений для вирішення тієї чи іншої задачі.
В
Генерація всіх перестановок n -елементного безлічі
Кількість різних перестановок множини, що складається з n елементів одно n !. У цьому неважко переконатися: на першому місці в перестановці може стояти будь-який з n елементів множини, після того, як ми на першому місці зафіксували небудь елемент, на другому місці може стояти будь-який з n - 1 залишився елемента і т.д. Таким чином, загальна кількість варіантів одно n ( n - 1) ( n - 2) ... 3 Г— 2 Г— 1 = n !. Тобто розглядати абсолютно всі перестановки ми можемо тільки у множест, що складаються з не більше, ніж 10 елементів.
Розглянемо рекурсивний алгоритм, що реалізує генерацію всіх перестановок в лексикографічному порядку. Такий порядок часто наімболее зручний при вирішенні олімпіадних завдань, так як спрощує застосування методу гілок і меж, який буде описаний нижче. Позначимо масив індексів елементів - p. Спочатку він заповнений числами 1, 2, ..., n , які в подальшому будуть мінятися місцями. Параметром i рекурсивної процедури Perm служить місце в масиві p, починаючи з якого повинні бути, отримані всі перестановки правій частині цього масиву. Ідея рекурсії, в даному випадку наступна: на i -му місці повинні побувати всі елементи масиву p з i -го по n -й і для кожного з цих елементів повинні бути отримані всі перестановки інших елементів, починаючи з ( i +1)-го місця, в лексикографічному порядку. Після отримання останньої з перестановок, починаючи с ( i +1)-го місця, вихідний порядок елементів повинен бути відновлений. br/>
{опис змінних збігається з наведеним вище}
procedure Permutations (n: integer);
procedure Perm (i: integer);
var j, k: integer;
begin
if i = n then
begin for j: = 1 to n do write (a [p [j]], ''...
