додати матеріал


Деякі способи розбиття множин

[ виправити ] текст може містити помилки, будь ласка перевіряйте перш ніж використовувати.

Введення
У наш бурхливо розвивається століття, здавалося б, всі алгоритми, які можна придумати, вже придумані. Але іноді зустрічаються завдання, для яких немає відповідних алгоритмів. Можливо, тому, що завдання рідко зустрічається або, швидше за все для цього завдання немає ефективних алгоритмів (а, швидше за все, їх і зовсім не існує).
У цій роботі буде обговорюватися тема розбиття множин.
В [1] автор дає кілька таких алгоритмів: генерування всіх підмножин n-елементної множини, генерування всіх k-елементних підмножин множини {1, ..., n} в лексикографічному порядку, генерування всіх розбиттів множини {1, ..., n} (на цьому алгоритмі зупинимося докладніше), знаходження всіх розбиття числа.
Перший з цих алгоритмів використовує ідею бінарного коду Грея, інші засновані на видаленні або додавання одного елемента. Останній алгоритм використовує схему розбивки більшого числа на менші числа.
Постановка завдання
Формулювання першого завдання, яку ми розглянемо, виглядає так: необхідно згенерувати всі розбиття множини, що містить n елементів.
Для формулювання другого завдання необхідно ввести деякі поняття.
Отже, дано безліч, що складається з n елементів. Кожен елемент цієї множини утворює деяке поняття. Два або більше поняття можуть бути об'єднані в нове поняття. Відмінна риса понять - взяття їх у круглі дужки.
Завдання виглядає так: згенерувати всі поняття, які можуть бути утворені з n елементів. Наприклад, для n = 3 маємо такі поняття (круглі дужки на початку і в кінці опущені для стислості): (*)**, (*)(*)*, (*)(*)(*), (**) *, (**)(*), ((*)*)*, ((*)*)(*), ((*)(*))*, ((*)(*))(*).
Математичне обгрунтування

Під розбивкою n-елементної множини Х на k блоків будемо розуміти довільне сімейство , Таке, що для 1 £ І <j £ k і для 1 £ i £ k. Підмножини будемо називати блоками сімейства π. Безліч всіх розбиттів множини Х на k блоків будемо позначати , А множина всіх розбиття через П (Х). Очевидно, що (Більше того, є розбиттям множини П (Х)).
Число Стірлінга другого роду S (n, k) визначається як число розбиття n-елементної множини на k блоків:
де | X | = n.
Очевидно, що 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.
Ось інша рекурентна залежність:
для k ≥ 2. (4)
Для доказу тотожності розглянемо безліч всіх розбиття S (n, k) множини Х = {1, ..., n}. Це безліч розпадається на різні класи, що відповідають різним підмножиною множини Х, які є блоками, які містять елемент n. Відзначимо, що для кожного b-елементного підмножини містить елемент n, існує в точності S (nb, k-1) розбиттів множини Х на k блоків, що містять В як блоку. Дійсно, кожне таке розбиття однозначно відповідає розбиття множини Х \ В на k-1 блоків. b-елементне безліч містить елемент n, можна вибрати способами; таким чином,

Число Белла визначається як число всіх розбиття n-елементної множини
де | X | = n.
Іншими словами,

Доведемо рекуррентную залежність, пов'язану з числами Белла:
(5)
(Приймаємо ). Доведення проводиться аналогічно докази тотожності (4). Безліч всіх розбиттів множини Х = {1, ..., n +1} можна розбити на різні класи в залежності від блоку В, що містить елемент n +1, або - що рівнозначно - в залежності від багатьох Х \ В. Для кожного безлічі існує в точності розбиттів множини Х, що містять В як блоку. Групуючи наші класи в залежності від потужності множини Х \ В, отримуємо формулу (5).
Тепер опишемо алгоритм генерування всіх розбиттів множини.
Зазначимо, що кожне розбиття p множини {1, ..., n} однозначно визначає розбиття множини {1, ..., n-1}, що виникло з p після видалення елемента n з відповідного блоку (і видалення утворився простого блоку, якщо елемент n утворював одноелементні блок). Навпаки, якщо дано розбиття множини {1, ..., n-1}, легко знайти всі розбиття π множини {1, ..., n}, такі що , Тобто такі розбиття:

Якщо нам дано список всіх розбиттів множини {1, ..., n-1}, то список всіх розбиттів множини {1, ..., n}, будемо створювати, замінюючи кожне розбиття σ в списку на відповідну йому послідовність (6). Якщо звернути порядок послідовності (6) для кожного другого розбиття , То елемент 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. Послідовність розбиттів множини {1,2,3,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.
Література
1. В. Липський, Комбінаторика для програмістів, пров. з польської, М. - Світ, 1988
        
  
Додати в блог або на сайт

Цей текст може містити помилки.

Програмування, комп'ютери, інформатика і кібернетика | Курсова | 42.2кб. | скачати

Схожі роботи:
Деякі способи отримання спиртів
Целюліт і деякі способи корекції фігури
Деякі з причин виникнення професійних захворювань у домристов і способи їх усунення
Про категорії множин
Побудова скінченних множин
Розмірність кінцевих впорядкованих множин
Основні поняття алгебри множин
Алгоритмічні мови використання множин
Застосування теорії нечітких множин до фінансового аналізу підприємств
© Усі права захищені
написати до нас
Рейтинг@Mail.ru