Введення
У наш бурхливо розвивається століття, здавалося б, всі алгоритми, які можна придумати, вже придумані. Але іноді зустрічаються завдання, для яких немає відповідних алгоритмів. Можливо, тому, що завдання рідко зустрічається або, швидше за все для цього завдання немає ефективних алгоритмів (а, швидше за все, їх і зовсім не існує).
У цій роботі буде обговорюватися тема розбиття множин.
В [1] автор дає кілька таких алгоритмів: генерування всіх підмножин n-елементної множини, генерування всіх k-елементних підмножин множини {1, ..., n} в лексикографічному порядку, генерування всіх розбиттів множини {1, ..., n} (на цьому алгоритмі зупинимося докладніше), знаходження всіх розбиття числа.
Перший з цих алгоритмів використовує ідею бінарного коду Грея, інші засновані на видаленні або додавання одного елемента. Останній алгоритм використовує схему розбивки більшого числа на менші числа.
Постановка завдання
Формулювання першого завдання, яку ми розглянемо, виглядає так: необхідно згенерувати всі розбиття множини, що містить n елементів.
Для формулювання другого завдання необхідно ввести деякі поняття.
Отже, дано безліч, що складається з n елементів. Кожен елемент цієї множини утворює деяке поняття. Два або більше поняття можуть бути об'єднані в нове поняття. Відмінна риса понять - взяття їх у круглі дужки.
Завдання виглядає так: згенерувати всі поняття, які можуть бути утворені з n елементів. Наприклад, для n = 3 маємо такі поняття (круглі дужки на початку і в кінці опущені для стислості): (*)**, (*)(*)*, (*)(*)(*), (**) *, (**)(*), ((*)*)*, ((*)*)(*), ((*)(*))*, ((*)(*))(*).
Математичне обгрунтування
Під розбивкою n-елементної множини Х на k блоків будемо розуміти довільне сімейство
Число Стірлінга другого роду S (n, k) визначається як число розбиття n-елементної множини на k блоків:
Очевидно, що S (n, k) = 0 для k> n. Приймають також S (0,0) = 1, так як пусте сімейство блоків є відповідно до визначення розбивкою порожньої множини. З числами Стірлінга другого порядку пов'язано багато цікавих тотожностей:
S (n, k) = S (n-1, k-1) + kS (n-1, k) для 0 <k <n, (1)
S (n, n) = 1 для n ≥ 0, (2)
S (n, 0) = 0 для n> 0. (3)
Формули (2) та (3) очевидні. Для доказу формули (1) розглянемо безліч всіх розбиттів множини {1, ..., n} на k блоків. Це безліч розпадається на два різних класи: тих розбиттів, які містять одноелементні блок {n}, і тих розбиття, для яких n є елементом більшого (принаймні, двоелементною) блоку. Потужність першого класу дорівнює S (n-1, k-1), тобто така, яке число розбиття множини {1, ..., n-1} на (k-1) блоків. Потужність іншого класу становить kS (n-1, k), оскільки кожному розбиття множини {1, ..., n-1} на k блоків відповідає в цьому класі в точності k розбиття, утворених додаванням елемента n по черзі до кожного блоку.
Формули (1) - (3) дозволяють легко обчислювати значення S (n, k) навіть для великих значень n і k.
Ось інша рекурентна залежність:
Для доказу тотожності розглянемо безліч всіх розбиття S (n, k) множини Х = {1, ..., n}. Це безліч розпадається на різні класи, що відповідають різним підмножиною множини Х, які є блоками, які містять елемент n. Відзначимо, що для кожного b-елементного підмножини
Число Белла
Іншими словами,
Доведемо рекуррентную залежність, пов'язану з числами Белла:
(Приймаємо
Тепер опишемо алгоритм генерування всіх розбиттів множини.
Зазначимо, що кожне розбиття p множини {1, ..., n} однозначно визначає розбиття
Якщо нам дано список
Розбиття множини {1, ..., n} ми будемо представляти за допомогою послідовності блоків, впорядкованої за зростанням самого маленького елемента в блоці. Цей найменший елемент блоку ми будемо називати номером блоку. Відзначимо, що номери сусідніх блоків, взагалі кажучи, не є сусідніми натуральними числами. У цьому алгоритмі ми будемо використовувати змінні divd [і], sled [і], 1 ≤ І ≤ n, що містять відповідно номер попереднього і номер наступного блоку з номером і (sled [і] = 0, якщо блок з номером І є останнім блоком розбиття). Для кожного елемента І, 1 ≤ І ≤ n, номер блоку, що містить елемент І, буде зберігатися у змінній blok [і], напрям, в якому «рухається» елемент І, буде закодовано в булевою змінної wper [і] (wper [і ] = true, якщо І рухається вперед).
Можна показати, що середня кількість кроків, необхідних для побудови кожного наступного розбиття, обмежена постійною, не залежної від n (звичайно, якщо не враховувати число кроків, необхідних для написання розбиття).
Табл.1. Послідовність розбиттів множини {1,2,3,4}
Наведемо тепер алгоритм розв'язання задачі про перерахування всіх понять.
Рекурсивний алгоритм використовувати не можна, бо всі рішення підзадачі меншої розмірності необхідно скомбінувати з усіма рішеннями підзадачі залишилася розмірності. Тому, будемо просто перебирати всі варіанти.
Ідея така: зберігаємо всі розбиття меншої розмірності і комбінуємо їх так, щоб
1) вони не повторювалися;
2) кількість елементів нового розбиття не було б більше кількості елементів n.
Отже, нехай ми маємо два початкових стану: (*) та *. Для n = 2 маємо тільки одне вихідна поняття: (*)*. Для n = 3 необхідно скомбінувати всі відомі раніше стану з урахуванням умов 1) -2).
Умова 1) забезпечимо з таких міркувань: кожному елементу присвоїти порядковий номер і комбінувати поняття так, щоб порядковий номер наступного поняття не перевершував порядковий номер попереднього поняття, а також стежити, щоб виконувалася умова 2). Звідси видно, що повторень не буде, і ми перерахуємо всі поняття.
Для реалізації умови 2) необхідно кожному поняттю привласнити число, яке буде показувати кількість елементів цього стану.
Також необхідно мати деякий масив, кожен елемент якого буде вказувати на поняття, що відповідає номеру поняття у вихідному понятті. Елементи цього масиву будуть змінюватися, відповідно до перебором варіантів.
Для алгоритмів нам знадобляться поняття покажчиків і записів.
Запис у Pascal'е описується так:
<Імя_тіпа> = | <ім'я_змінної>: record
<Список полів та їх типів>
end;
Наприклад,
Var point: record
x, y: integer;
color: byte
end;
Звертаються до полів запису так:
Nx: = point.x + point.y;
Point. Color: = 3;
Покажчики описуються так:
<Імя_тіпа> = | <ім'я_змінної>: ^ <ім'я типу>
Наприклад, k: ^ integer - Покажчик на ціле. Звернення до вмісту покажчика: t: = k ^, а запис значення в комірку пам'яті, куди вказує k, виглядає так: k ^: = 10. Але, щоби використовувати покажчики, необхідно спочатку виділити пам'ять під них. Це робиться за допомогою команди new:
New (k);
Щоб звільнити пам'ять, якщо покажчик вже не буде потрібен, використовують
Dispose (k);
Оператори присвоювання, арифметичних операцій і циклів схожі в багатьох мовах, тому їх описувати не варто.
program razbienie_mnozhestwa (input, output);
var i, j, k, n: byte; wper: array [1 .. 255] of boolean;
sled, divd, blok: array [1 .. 255] of byte;
procedure write_razbienie; {процедура, що виписує розбиття на екран}
var
i, j: byte;
begin
j: = 1; {номер першого блоку}
repeat
write ('(');
for i: = j to n do if blok [i] = j then write (i, ''); {якщо число І з блоку j, то пишемо це число}
j: = sled [j]; {наступний за номером блок}
write (')');
until j = 0;
WRITELN
end;
begin
write ('input n:');
readln (n); {вводимо кількість елементів множини}
for i: = 1 to n do begin {будуємо розбиття {{1, ..., n}}}
blok [i]: = 1;
wper [i]: = true
end;
sled [1]: = 0;
write_razbienie; {виписати розбиття}
j: = n; {активний елемент}
while j> 1 do begin {завдання циклу - переміщення «активного» елемента j в сусідній блок - у попередній або наступний (в останньому випадку може виникнути необхідність створення нового блоку виду {j}, а потім визначення активного елементу у новоутвореному розбитті}
k: = blok [j]; {процес перенесення активного елемента; k - Номер активного блоку}
if wper [j] then begin {j рухається вперед}
if sled [k] = 0 then begin {k - останній блок}
sled [k]: = j; {j - одноелементні блок}
divd [j]: = k;
sled [j]: = 0
end;
if sled [k]> j then begin {j утворює новий блок}
divd [j]: = k; {всі блоки праворуч від блоку з номером k містять елементи, великі j. Звідси випливає, що j утворює новий одноелементні блок}
sled [j]: = sled [k];
divd [sled [j]]: = j;
sled [k]: = j
end;
blok [j]: = sled [k] {переносимо наш елемент в активний блок з номером k}
end
else begin {j рухається тому}
blok [j]: = divd [k]; {поміщаємо j в попередній блок}
if k = j then if sled [k] = 0 then sled [divd [k]]: = 0 else begin
sled [divd [k]]: = sled [k];
divd [sled [k]]: = divd [k]
end
end;
write_razbienie;
j: = n;
while (j> 1) and
((Wper [j] and (blok [j] = j)) or (not wper [j] and (blok [j] = 1))) do begin
wper [j]: = not wper [j];
dec (j)
end
end
end.
Кількість всіх розбиття можна порахувати використовуючи числа Белла і рекуррентную формулу (5).
1) тип k - покажчик на запис, поля якої: s - буде містити поняття; p - кількість елементів у понятті; next - посилання на таке поняття;
2) перемінні f, pot типу k; f - вказує на перше поняття, тобто на просте поняття *; pot - поточний поняття;
3) масив str1 типу k - буде містити посилання на кожне поняття в складеному понятті;
program dyscretics_optimisation (input, output);
uses crt;
const
max = 12;
r: byte = 0;
type
k = ^ el;
El = record
S: string;
P: 1 .. Max-1;
Next: k
End;
Label met;
Var
Pot, f, l: k;
Str1: array [1 .. Max] of k;
Pow: 2 .. Max;
K1, i, j, ll: 1 .. Max;
Sum: 0 .. Max;
Fil: text;
Ki: string [2];
begin
Readln (POW); {вводимо кількість простих понять}
Str (POW, ki);
Assign (fil, ki + '. Mvp'); {вийшли поняття будемо записувати в файл, що містить в своєму імені кількість елементів множини і з розширенням «. Mvp»}
Rewrite (fil);
New (f); {виділяємо пам'ять під перше поняття}
Pot: = f;
F ^. S :='*'; {і ініціалізували його}
F ^. P: = 1;
New (f ^. Next); {виділяємо пам'ять під друге поняття}
Pot: = f ^. Next;
Pot ^. S :='(*)'; {і також його инициализируем}
Pot ^. P: = 1;
Pot ^. Next: = nil;
for i: = 2 to POW do begin {основний цикл програми}
For j: = 1 to i do str 1 [j]: = f; {встановлюємо початкові покажчики поняття, розмірності І, на перше поняття}
If i = POW then str 1 [1]: = f ^. next; {якщо І дорівнює кількості елементів множини, то необхідно змінити покажчик на перше подпонятіе нашого поняття, так як вже зазначалося вище, поняття, що складається тільки з простих подпонятій виводити не треба. Але, такі поняття залишаємо для підзадач меншої розмірності, так як у комбінації з рішеннями інших підзадач, отримаємо вже поняття, яке містить не тільки прості поняття}
While str 1 [1] <> nil do begin {поки покажчик перший подпонятія не досягне кінця списку подпонятій виконувати}
New (pot ^. Next); {виділити пам'ять під чергове поняття}
Sum: = 0; {ця змінна служить в якості лічильника, який після наступного циклу буде містити кількість елементів у новому понятті}
K 1: = 1; {номер першого подпонятія. Перше подпонятіе має завжди, якщо можна так висловитися, «більш пізній адресу», або, точніше, все подпонятія, що йде за першим, отримані раніше або одночасно з ним. Це також стосується другого подпонятіе щодо третього, четвертого і т. д., третього щодо четвертого, п'ятого і т. д., і т. д.}
If i = pow then pot ^. next ^. s: =''else pot ^. next ^. s :='('; {якщо І дорівнює кількості елементів множини, то нам не потрібні дужки на початку (їх домовилися опустити)}
While sum <i do begin {поки кількість елементів у новому понятті менше розмірності підзадачі, виконати}
Pot ^. Next ^. S: = pot ^. Next ^. S + str 1 [k 1] ^. S; {Додати в поняття подпонятіе з номером k 1}
Sum: = sum + str 1 [k 1] ^. P; {додати розмірність, доданого подпонятія}
Inc (k 1); {збільшити k 1 на 1}
End;
If (sum> i) or (k 1 = 2) then begin {якщо кількість елементів отриманого поняття більше розмірності задачі або k 1 = 2, тобто додано тільки одне поняття в подпонятіе, то, щоб уникнути зайвих дужок і неправильних рішень виконати}
Dispose (pot ^. Next); {звільнити пам'ять, займану цим «неправильним» поняттям}
Pot ^. Next: = nil; {вказати, що попереднє поняття було останнім}
If k 1 = 2 then break {якщо k 1 = 2, то вийти з основного циклу програми}
End
Else begin
If i = POW then begin {якщо розмірність поточної підзадачі дорівнює розмірності основного завдання, то}
Writeln (fil, pot ^. Next ^. S); {записати поняття в файл}
Writeln (pot ^. Next ^. S); {і вивести на екран}
Dispose (pot ^. Next); {звільнити пам'ять, займану поняттям, так як поняття розмірності задачі нам більше не знадобляться}
Pot ^. Next: = nil
End
Else begin {інакше инициализируем поняття до кінця}
Pot: = pot ^. Next;
Pot ^. S: = pot ^. S +')'; {закриваємо дужку}
Pot ^. Next: = nil; {вказуємо, що це поняття останнє в списку}
Pot ^. P: = I {вказуємо кількість елементів, що містяться в понятті}
End
End;
For j: = k 1-1 downto 2 do begin {k 1 зараз показує кількість подпонятій останнього поняття плюс 1. Тому в цьому циклі, який спробує визначити наступну комбінацію понять і використовується змінна k 1. Ця частина програми розглядає випадок, коли подпонятія будуть ставати не наступним за списком подпонятіямі (принаймні не всі), а будуть відбуватися інші переходи. Тобто цей цикл розрахований на те, щоб не дозволити подпонятію з великим номером за списком у понятті бути великим за абсолютною адресою (за часом створення)}
If (str1 [j] ^. Next = str1 [j-1]) and (str1 [j +1] = str1 [j]) or ((j = k1-1) and (str1 [j] <>
Str 1 [j -1])) then begin {якщо за подпонятіем з номером j за списком слід подпонятіе з номером j -1 і подпонятія з номером j і j +1 збігаються, або j дорівнює кількості подпонятій і останні два поняття збігаються (порівняння йде за абсолютними адресами розташування понять в пам'яті), то}
str 1 [j]: = str 1 [j] ^. next; {подпонятіе з номером j переходить на наступне за списком подпонятіе}
For j: = J +1 to k 1-1 do str 1 [j]: = f; {а всі наступні подпонятія, стають рівними першому (елементарного) подпонятію}
goto met {хоча застосування оператора безумовного переходу вважається поганим стилем програмування, але тут він виправданий, щоб не заплутувати програму новими циклами}
End;
End;
For j: = k 1-1 downto 2 do begin { нов и й цикл, який перемкне відповідні подпонятія. Ми виділяємо це в новий цикл, тому що потрібно було перевірити на наявність "граничних" переходів (див. попередній цикл)}
If str 1 [j] <> str 1 [j -1] then begin {якщо подпонятія з номерами j і (j -1) не збігаються, то}
Str 1 [j]: = str 1 [j] ^. Next; {подпонятіе з номером j стає наступним за списком (часу створення подпонятіем)}
For j: = j +1 to k 1 do str 1 [j]: = f; {а всі йдуть за ним подпонятія в списку подпонятій, складових поняття стають елементарними}
goto met {виходимо з циклу}
End
End;
Str 1 [1]: = str 1 [1] ^. Next; {якщо не виконалися умови попередніх двох циклів, то час перемикати першому подпонятіе}
for j: = 2 to i do str 1 [j]: = f; {і, відповідно, наступні подпонятія зробити елементарними}
Met: end
End;
Close (fil); {закр ить файл}
Repeat {і}
Pot: = f ^. Next;
Dispose (f); {звільнити пам'ять, займану списком всіх можливих подпонятій}
F: = pot
Until f <> nil
end.
У наш бурхливо розвивається століття, здавалося б, всі алгоритми, які можна придумати, вже придумані. Але іноді зустрічаються завдання, для яких немає відповідних алгоритмів. Можливо, тому, що завдання рідко зустрічається або, швидше за все для цього завдання немає ефективних алгоритмів (а, швидше за все, їх і зовсім не існує).
У цій роботі буде обговорюватися тема розбиття множин.
В [1] автор дає кілька таких алгоритмів: генерування всіх підмножин n-елементної множини, генерування всіх k-елементних підмножин множини {1, ..., n} в лексикографічному порядку, генерування всіх розбиттів множини {1, ..., n} (на цьому алгоритмі зупинимося докладніше), знаходження всіх розбиття числа.
Перший з цих алгоритмів використовує ідею бінарного коду Грея, інші засновані на видаленні або додавання одного елемента. Останній алгоритм використовує схему розбивки більшого числа на менші числа.
Постановка завдання
Формулювання першого завдання, яку ми розглянемо, виглядає так: необхідно згенерувати всі розбиття множини, що містить n елементів.
Для формулювання другого завдання необхідно ввести деякі поняття.
Отже, дано безліч, що складається з n елементів. Кожен елемент цієї множини утворює деяке поняття. Два або більше поняття можуть бути об'єднані в нове поняття. Відмінна риса понять - взяття їх у круглі дужки.
Завдання виглядає так: згенерувати всі поняття, які можуть бути утворені з n елементів. Наприклад, для n = 3 маємо такі поняття (круглі дужки на початку і в кінці опущені для стислості): (*)**, (*)(*)*, (*)(*)(*), (**) *, (**)(*), ((*)*)*, ((*)*)(*), ((*)(*))*, ((*)(*))(*).
Математичне обгрунтування
Під розбивкою n-елементної множини Х на k блоків будемо розуміти довільне сімейство
Число Стірлінга другого роду S (n, k) визначається як число розбиття n-елементної множини на k блоків:
Очевидно, що S (n, k) = 0 для k> n. Приймають також S (0,0) = 1, так як пусте сімейство блоків є відповідно до визначення розбивкою порожньої множини. З числами Стірлінга другого порядку пов'язано багато цікавих тотожностей:
S (n, k) = S (n-1, k-1) + kS (n-1, k) для 0 <k <n, (1)
S (n, n) = 1 для n ≥ 0, (2)
S (n, 0) = 0 для n> 0. (3)
Формули (2) та (3) очевидні. Для доказу формули (1) розглянемо безліч всіх розбиттів множини {1, ..., n} на k блоків. Це безліч розпадається на два різних класи: тих розбиттів, які містять одноелементні блок {n}, і тих розбиття, для яких n є елементом більшого (принаймні, двоелементною) блоку. Потужність першого класу дорівнює S (n-1, k-1), тобто така, яке число розбиття множини {1, ..., n-1} на (k-1) блоків. Потужність іншого класу становить kS (n-1, k), оскільки кожному розбиття множини {1, ..., n-1} на k блоків відповідає в цьому класі в точності k розбиття, утворених додаванням елемента n по черзі до кожного блоку.
Формули (1) - (3) дозволяють легко обчислювати значення S (n, k) навіть для великих значень n і k.
Ось інша рекурентна залежність:
Для доказу тотожності розглянемо безліч всіх розбиття S (n, k) множини Х = {1, ..., n}. Це безліч розпадається на різні класи, що відповідають різним підмножиною множини Х, які є блоками, які містять елемент n. Відзначимо, що для кожного b-елементного підмножини
Число Белла
Іншими словами,
Доведемо рекуррентную залежність, пов'язану з числами Белла:
(Приймаємо
Тепер опишемо алгоритм генерування всіх розбиттів множини.
Зазначимо, що кожне розбиття p множини {1, ..., n} однозначно визначає розбиття
Якщо нам дано список
Розбиття множини {1, ..., n} ми будемо представляти за допомогою послідовності блоків, впорядкованої за зростанням самого маленького елемента в блоці. Цей найменший елемент блоку ми будемо називати номером блоку. Відзначимо, що номери сусідніх блоків, взагалі кажучи, не є сусідніми натуральними числами. У цьому алгоритмі ми будемо використовувати змінні divd [і], sled [і], 1 ≤ І ≤ n, що містять відповідно номер попереднього і номер наступного блоку з номером і (sled [і] = 0, якщо блок з номером І є останнім блоком розбиття). Для кожного елемента І, 1 ≤ І ≤ n, номер блоку, що містить елемент І, буде зберігатися у змінній blok [і], напрям, в якому «рухається» елемент І, буде закодовано в булевою змінної wper [і] (wper [і ] = true, якщо І рухається вперед).
Можна показати, що середня кількість кроків, необхідних для побудови кожного наступного розбиття, обмежена постійною, не залежної від n (звичайно, якщо не враховувати число кроків, необхідних для написання розбиття).
| (1 2 3 4) (1 2 3) (4) (1 2) (3) (4) (1 2) (3 4) (1 2 4) (3) (1 4) (2) (3) (1) (2 4) (3) (1) (2) (3 4) (1) (2) (3) (4) (1) (2 3) (4) (1) (2 3 4) (1 4) (2 3) (1 3 4) (2) (1 3) (2 4) (1 3) (2) (4) |
Наведемо тепер алгоритм розв'язання задачі про перерахування всіх понять.
Рекурсивний алгоритм використовувати не можна, бо всі рішення підзадачі меншої розмірності необхідно скомбінувати з усіма рішеннями підзадачі залишилася розмірності. Тому, будемо просто перебирати всі варіанти.
Ідея така: зберігаємо всі розбиття меншої розмірності і комбінуємо їх так, щоб
1) вони не повторювалися;
2) кількість елементів нового розбиття не було б більше кількості елементів n.
Отже, нехай ми маємо два початкових стану: (*) та *. Для n = 2 маємо тільки одне вихідна поняття: (*)*. Для n = 3 необхідно скомбінувати всі відомі раніше стану з урахуванням умов 1) -2).
Умова 1) забезпечимо з таких міркувань: кожному елементу присвоїти порядковий номер і комбінувати поняття так, щоб порядковий номер наступного поняття не перевершував порядковий номер попереднього поняття, а також стежити, щоб виконувалася умова 2). Звідси видно, що повторень не буде, і ми перерахуємо всі поняття.
Для реалізації умови 2) необхідно кожному поняттю привласнити число, яке буде показувати кількість елементів цього стану.
Також необхідно мати деякий масив, кожен елемент якого буде вказувати на поняття, що відповідає номеру поняття у вихідному понятті. Елементи цього масиву будуть змінюватися, відповідно до перебором варіантів.
Мова програмування
Для реалізації алгоритмів була вибрана мова програмування Turbo Pascal 7.0. У цій мові є всі необхідні кошти для цих алгоритмів, і сама мова є простим для розуміння. Тому вибір ліг саме на нього.Для алгоритмів нам знадобляться поняття покажчиків і записів.
Запис у Pascal'е описується так:
<Імя_тіпа> = | <ім'я_змінної>: record
<Список полів та їх типів>
end;
Наприклад,
Var point: record
x, y: integer;
color: byte
end;
Звертаються до полів запису так:
Nx: = point.x + point.y;
Point. Color: = 3;
Покажчики описуються так:
<Імя_тіпа> = | <ім'я_змінної>: ^ <ім'я типу>
Наприклад, k: ^ integer - Покажчик на ціле. Звернення до вмісту покажчика: t: = k ^, а запис значення в комірку пам'яті, куди вказує k, виглядає так: k ^: = 10. Але, щоби використовувати покажчики, необхідно спочатку виділити пам'ять під них. Це робиться за допомогою команди new:
New (k);
Щоб звільнити пам'ять, якщо покажчик вже не буде потрібен, використовують
Dispose (k);
Оператори присвоювання, арифметичних операцій і циклів схожі в багатьох мовах, тому їх описувати не варто.
Реалізація алгоритмів
Генерування розбиттів множини
У табл.1 представлені розбиття для n = 4, що генеруються наступним алгоритмом:program razbienie_mnozhestwa (input, output);
var i, j, k, n: byte; wper: array [1 .. 255] of boolean;
sled, divd, blok: array [1 .. 255] of byte;
procedure write_razbienie; {процедура, що виписує розбиття на екран}
var
i, j: byte;
begin
j: = 1; {номер першого блоку}
repeat
write ('(');
for i: = j to n do if blok [i] = j then write (i, ''); {якщо число І з блоку j, то пишемо це число}
j: = sled [j]; {наступний за номером блок}
write (')');
until j = 0;
WRITELN
end;
begin
write ('input n:');
readln (n); {вводимо кількість елементів множини}
for i: = 1 to n do begin {будуємо розбиття {{1, ..., n}}}
blok [i]: = 1;
wper [i]: = true
end;
sled [1]: = 0;
write_razbienie; {виписати розбиття}
j: = n; {активний елемент}
while j> 1 do begin {завдання циклу - переміщення «активного» елемента j в сусідній блок - у попередній або наступний (в останньому випадку може виникнути необхідність створення нового блоку виду {j}, а потім визначення активного елементу у новоутвореному розбитті}
k: = blok [j]; {процес перенесення активного елемента; k - Номер активного блоку}
if wper [j] then begin {j рухається вперед}
if sled [k] = 0 then begin {k - останній блок}
sled [k]: = j; {j - одноелементні блок}
divd [j]: = k;
sled [j]: = 0
end;
if sled [k]> j then begin {j утворює новий блок}
divd [j]: = k; {всі блоки праворуч від блоку з номером k містять елементи, великі j. Звідси випливає, що j утворює новий одноелементні блок}
sled [j]: = sled [k];
divd [sled [j]]: = j;
sled [k]: = j
end;
blok [j]: = sled [k] {переносимо наш елемент в активний блок з номером k}
end
else begin {j рухається тому}
blok [j]: = divd [k]; {поміщаємо j в попередній блок}
if k = j then if sled [k] = 0 then sled [divd [k]]: = 0 else begin
sled [divd [k]]: = sled [k];
divd [sled [k]]: = divd [k]
end
end;
write_razbienie;
j: = n;
while (j> 1) and
((Wper [j] and (blok [j] = j)) or (not wper [j] and (blok [j] = 1))) do begin
wper [j]: = not wper [j];
dec (j)
end
end
end.
Кількість всіх розбиття можна порахувати використовуючи числа Белла і рекуррентную формулу (5).
Генерування всіх понять
Для реалізації даного завдання на Pascal'е вводимо наступні типи даних і змінних:1) тип k - покажчик на запис, поля якої: s - буде містити поняття; p - кількість елементів у понятті; next - посилання на таке поняття;
2) перемінні f, pot типу k; f - вказує на перше поняття, тобто на просте поняття *; pot - поточний поняття;
3) масив str1 типу k - буде містити посилання на кожне поняття в складеному понятті;
program dyscretics_optimisation (input, output);
uses crt;
const
max = 12;
r: byte = 0;
type
k = ^ el;
El = record
S: string;
P: 1 .. Max-1;
Next: k
End;
Label met;
Var
Pot, f, l: k;
Str1: array [1 .. Max] of k;
Pow: 2 .. Max;
K1, i, j, ll: 1 .. Max;
Sum: 0 .. Max;
Fil: text;
Ki: string [2];
begin
Readln (POW); {вводимо кількість простих понять}
Str (POW, ki);
Assign (fil, ki + '. Mvp'); {вийшли поняття будемо записувати в файл, що містить в своєму імені кількість елементів множини і з розширенням «. Mvp»}
Rewrite (fil);
New (f); {виділяємо пам'ять під перше поняття}
Pot: = f;
F ^. S :='*'; {і ініціалізували його}
F ^. P: = 1;
New (f ^. Next); {виділяємо пам'ять під друге поняття}
Pot: = f ^. Next;
Pot ^. S :='(*)'; {і також його инициализируем}
Pot ^. P: = 1;
Pot ^. Next: = nil;
for i: = 2 to POW do begin {основний цикл програми}
For j: = 1 to i do str 1 [j]: = f; {встановлюємо початкові покажчики поняття, розмірності І, на перше поняття}
If i = POW then str 1 [1]: = f ^. next; {якщо І дорівнює кількості елементів множини, то необхідно змінити покажчик на перше подпонятіе нашого поняття, так як вже зазначалося вище, поняття, що складається тільки з простих подпонятій виводити не треба. Але, такі поняття залишаємо для підзадач меншої розмірності, так як у комбінації з рішеннями інших підзадач, отримаємо вже поняття, яке містить не тільки прості поняття}
While str 1 [1] <> nil do begin {поки покажчик перший подпонятія не досягне кінця списку подпонятій виконувати}
New (pot ^. Next); {виділити пам'ять під чергове поняття}
Sum: = 0; {ця змінна служить в якості лічильника, який після наступного циклу буде містити кількість елементів у новому понятті}
K 1: = 1; {номер першого подпонятія. Перше подпонятіе має завжди, якщо можна так висловитися, «більш пізній адресу», або, точніше, все подпонятія, що йде за першим, отримані раніше або одночасно з ним. Це також стосується другого подпонятіе щодо третього, четвертого і т. д., третього щодо четвертого, п'ятого і т. д., і т. д.}
If i = pow then pot ^. next ^. s: =''else pot ^. next ^. s :='('; {якщо І дорівнює кількості елементів множини, то нам не потрібні дужки на початку (їх домовилися опустити)}
While sum <i do begin {поки кількість елементів у новому понятті менше розмірності підзадачі, виконати}
Pot ^. Next ^. S: = pot ^. Next ^. S + str 1 [k 1] ^. S; {Додати в поняття подпонятіе з номером k 1}
Sum: = sum + str 1 [k 1] ^. P; {додати розмірність, доданого подпонятія}
Inc (k 1); {збільшити k 1 на 1}
End;
If (sum> i) or (k 1 = 2) then begin {якщо кількість елементів отриманого поняття більше розмірності задачі або k 1 = 2, тобто додано тільки одне поняття в подпонятіе, то, щоб уникнути зайвих дужок і неправильних рішень виконати}
Dispose (pot ^. Next); {звільнити пам'ять, займану цим «неправильним» поняттям}
Pot ^. Next: = nil; {вказати, що попереднє поняття було останнім}
If k 1 = 2 then break {якщо k 1 = 2, то вийти з основного циклу програми}
End
Else begin
If i = POW then begin {якщо розмірність поточної підзадачі дорівнює розмірності основного завдання, то}
Writeln (fil, pot ^. Next ^. S); {записати поняття в файл}
Writeln (pot ^. Next ^. S); {і вивести на екран}
Dispose (pot ^. Next); {звільнити пам'ять, займану поняттям, так як поняття розмірності задачі нам більше не знадобляться}
Pot ^. Next: = nil
End
Else begin {інакше инициализируем поняття до кінця}
Pot: = pot ^. Next;
Pot ^. S: = pot ^. S +')'; {закриваємо дужку}
Pot ^. Next: = nil; {вказуємо, що це поняття останнє в списку}
Pot ^. P: = I {вказуємо кількість елементів, що містяться в понятті}
End
End;
For j: = k 1-1 downto 2 do begin {k 1 зараз показує кількість подпонятій останнього поняття плюс 1. Тому в цьому циклі, який спробує визначити наступну комбінацію понять і використовується змінна k 1. Ця частина програми розглядає випадок, коли подпонятія будуть ставати не наступним за списком подпонятіямі (принаймні не всі), а будуть відбуватися інші переходи. Тобто цей цикл розрахований на те, щоб не дозволити подпонятію з великим номером за списком у понятті бути великим за абсолютною адресою (за часом створення)}
If (str1 [j] ^. Next = str1 [j-1]) and (str1 [j +1] = str1 [j]) or ((j = k1-1) and (str1 [j] <>
Str 1 [j -1])) then begin {якщо за подпонятіем з номером j за списком слід подпонятіе з номером j -1 і подпонятія з номером j і j +1 збігаються, або j дорівнює кількості подпонятій і останні два поняття збігаються (порівняння йде за абсолютними адресами розташування понять в пам'яті), то}
str 1 [j]: = str 1 [j] ^. next; {подпонятіе з номером j переходить на наступне за списком подпонятіе}
For j: = J +1 to k 1-1 do str 1 [j]: = f; {а всі наступні подпонятія, стають рівними першому (елементарного) подпонятію}
goto met {хоча застосування оператора безумовного переходу вважається поганим стилем програмування, але тут він виправданий, щоб не заплутувати програму новими циклами}
End;
End;
For j: = k 1-1 downto 2 do begin { нов и й цикл, який перемкне відповідні подпонятія. Ми виділяємо це в новий цикл, тому що потрібно було перевірити на наявність "граничних" переходів (див. попередній цикл)}
If str 1 [j] <> str 1 [j -1] then begin {якщо подпонятія з номерами j і (j -1) не збігаються, то}
Str 1 [j]: = str 1 [j] ^. Next; {подпонятіе з номером j стає наступним за списком (часу створення подпонятіем)}
For j: = j +1 to k 1 do str 1 [j]: = f; {а всі йдуть за ним подпонятія в списку подпонятій, складових поняття стають елементарними}
goto met {виходимо з циклу}
End
End;
Str 1 [1]: = str 1 [1] ^. Next; {якщо не виконалися умови попередніх двох циклів, то час перемикати першому подпонятіе}
for j: = 2 to i do str 1 [j]: = f; {і, відповідно, наступні подпонятія зробити елементарними}
Met: end
End;
Close (fil); {закр ить файл}
Repeat {і}
Pot: = f ^. Next;
Dispose (f); {звільнити пам'ять, займану списком всіх можливих подпонятій}
F: = pot
Until f <> nil
end.