Введення
У наш бурхливо розвивається століття, здавалося б, всі алгоритми, які можна придумати, вже придумані. Але іноді зустрічаються завдання, для яких немає відповідних алгоритмів. Бути може тому, що завдання рідко зустрічається або, скоріше всього для цієї задачі немає ефективних алгоритмів (А, швидше за все, їх і зовсім не існує). p> У цій роботі буде обговорюватися тема разбиений множин.
У [1] автор дає кілька таких алгоритмів: генерування всіх підмножин n-елементного безлічі, генерування всіх k-елементних підмножин множини {1, ..., n} у лексикографічному порядку, генерування всіх розбиттів множини {1, ..., n} (на цьому алгоритмі зупинимося детальніше), знаходження всіх розбиттів числа.
Перший з цих алгоритмів використовує ідею бінарного коду Грея , решта засновані на видаленні або додаванні одного елемента. Останній алгоритм використовує схему розбиття більшого числа на менші числа. br/>
Постановка завдання
Формулювання першого завдання, яку ми розглянемо, виглядає так: необхідно згенерувати всі розбиття множини, що містить n елементів.
Для формулювання другого завдання необхідно ввести деякі поняття.
Отже, дано безліч, що складається з n елементів. Кожен елемент цієї множини утворює деяке поняття. Два або більше поняття можуть бути об'єднані в нове поняття. Відмінна риса понять - взяття їх в круглі дужки. p> Завдання виглядає так: згенерувати всі поняття, які можуть бути утворені з n елементів. Наприклад, для n = 3 маємо такі поняття (круглі дужки на початку і в кінці опущені для стислості): (*) **, (*) (*) *, (*) (*) (*), (**) *, (**) (*), ((*) *) *, ((*) *) (*), ((*) (*)) *, ((*) (*)) (*). br/>
Математичне обгрунтування
В
Під розбиттям n-елементного безлічі Х на k блоків будемо розуміти довільне сімейство, таке, що для 1 ВЈ и
Число Стірлінга другого роду 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
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> Тепер опишемо алгоритм генерування всіх розбиттів множини.
Зазначимо, що кожне розбиття p множини {1, ..., n} однозначно визначає розбиття множини {1, ..., n-1}, виникло з p після...
