18 Симоненко Е.А. Дискретная математика. Лекции
(x1+ x2+ …+ xk )n= ∑ Pn (r1, r2, … ,rk )xr11 xr22 … xrkk ,r1+ r2+ …+ r k=n .
r1, r2, … ,rk
Разбиения
Разбиением множества X, X =n , на k подмножеств называется семейство множеств таких,
что X 1 X 2 … X k= X , X i ∩X j= ,1 i< j k , X i≠ , 1 i k . Разбиение множества X на k обозначают Π k ( X ) , а множество всех разбиений – Π (X ) Например, выпишем все
разбиения множества X ={1, 2,3} : на одно: {{1, 2,3}} ;
на два: {{1}, {2, 3}} , {{2}, {1, 3}} , {{3}, {1, 2}} ; на три: {{1}, {2}, {3}} .
Количество |
элементов |
в |
разбиении |
Π k (X ) |
обозначают |
S nk |
и |
называют числами |
||||
Стирлинга второго рода. |
|
|
|
|
|
|
|
|
||||
Очевидно, что S n1=1 и S nn=1 . Полагаем также, что S 00=0 и S n0=0 . |
|
|
||||||||||
Нетрудно доказать следующую формулу: |
|
|
|
|
|
|
||||||
S nk =S nk−−11+ k S nk−1 , где |
0< k < n . |
|
|
|
|
|
|
|
||||
Например, |
это |
можно |
сделать |
так. |
Рассмотрим в |
семействе |
разбиений множества |
|||||
X ={x1, x2, …, xn } такие, где присутствует элемент |
{xn} |
и где он отсутствует. Количество |
||||||||||
элементов с |
{xn} равно |
S nk−−11 (так как xn входит только в подмножество |
{xn} , то остальные |
|||||||||
элементы семейства |
образуют |
семейство всех |
разбиений |
множества {x1, x2, …, xn −1 } , |
||||||||
{x1, x2, … , xn−1}=n−1 |
по |
k −1 ). Количество элементов второго вида можно посчитать так. |
||||||||||
Рассмотрим |
все |
разбиения множества |
{x1, x2, … , xn−1}=n−1 |
по |
k, их количество равно |
|||||||
S kn−1 . Тогда добавляя по очереди к каждому из элементов разбиения, коих k, элемент xn , получим, что их общее количество равно k Skn−1 .
Есть и другая формула для вычисления количества разбиений:
n−1
S kn= ∑ Cin−1 S ki −1 , k 2 . i=k−1
Эту формулу мы доказывать не будем. (См. [Окулов: ДМ].)
Рассмотрим теперь всевозможные разбиения множества X, X =n . Очевидно, что
n
Π ( X ) =∑ S kn .
k=0
Количество всех разбиений Π ( X ) называют также числами Белла и обозначают Bn . Для них справедлива следующая рекуррентная формула:
n
Bn+ 1=∑Ckn Bk . k =0
Генерация всех перестановок
Перестановки часто встречаются в задачах, решаемых полным перебором. Поэтому уметь реализовывать алгоритм генерации всех перестановок – важно. (Хотя, например, в C++, в его стандартной библиотеке, есть готовый алгоритм под названием next_permutation().)
Комбинаторная теория |
19 |
В принципе, придумать алгоритм, генерирующий все перестановки, не сложно. Посмотрим
на примере, как это можно сделать. Пусть дано множество |
X ={a ,b ,c} . Выпишем все его |
перестановки, соблюдая некоторую последовательность: |
(a ,b ,c) , (b ,a ,c) , (b ,c , a) , |
(c ,b , a) , (c , a ,b) , (a ,c ,b) . |
|
Идея такого алгоритма проста: |
|
–сначала упорядочиваем элементы перестановки в соответствии с заведённом на исходном множестве порядком; таким образом получаем первую перестановку;
–затем поочерёдно обмениваем значениями соседние элементы перестановки: первый со вторым, второй с третьим, …, предпоследний с последним;
–повторяем эту последовательность обменов до тех пор, пока не получим исходную перестановку.
Применим этот алгоритм к нашему примеру ещё раз (здесь и ниже полужирным выделены элементы, значения которых должны быть обменены):
(a , b ,c)→(b , a ,c)
(b , a , c)→(b , c , a) (b , c ,a)→(c , b ,a) (c , b , a)→(c , a , b) (c , a ,b)→(a , c ,b) (a , c , b)→(a , b , c)
Но часто требуется, чтобы генерируемые перестановки были упорядочены. Для этого на множестве всех перестановок вводится так называемый лексикографический порядок:
перестановка x |
лексикографически меньше y, x< y , |
если существует такое j, |
j 1 , что |
||||
x j < y j и |
xi = yi |
для всех |
i<t . Такой порядок подобен порядку слов в словарях, поэтому у |
||||
него такое название. |
|
|
|
|
|
||
Например, |
пусть дано |
множество |
X ={a ,b , c} . |
Выпишем все |
его перестановки в |
||
лексикографическом порядке: (a ,b ,c) , |
(a ,c ,b) , (b ,a ,c) , (b ,c , a) , |
(c , a ,b) , |
(c ,b , a) . |
||||
Из этого пример нетрудно уловить основную идею алгоритма генерации всех перестановок в лексикографическом порядке:
–сначала упорядочиваем элементы перестановки в соответствии с заведённом на исходном множестве порядком; таким образом получаем первую перестановку;
–затем просматриваем текущую перестановку с конца и ищем первый попавшийся элемент, нарушающий монотонность следования элементов справа налево;
–вновь просматриваем текущую перестановку с конца и ищем первый попавшийся элемент, больший чем найденный на предыдущем шаге;
–обмениваем эти два элемента значениями;
–упорядочиваем ту часть перестановки, что следует за найденным элементом;
–повторяем эту последовательность действий до тех пор, пока не получим перестановку, упорядоченная в обратном порядке.
Применим этот алгоритм к нашему примеру ещё раз:
20 |
Симоненко Е.А. Дискретная математика. Лекции |
(a , b ,c)→(a , b , c)→(a , c , b)→(a ,c , b)→(a ,c ,b)
(a , c ,b)→(a , c , b)→(b ,c , a)→(b ,c , a)→(b ,a ,c) (b , a ,c)→(b , a , c)→(b , c , a)→(b ,c , a)→(b ,c ,a ) (b , c ,a)→(b , c ,a)→(c , b , a)→(c ,b , a)→(c ,a ,b) (c , a ,b)→(c , a , b)→(c , b , a)→(c ,b , a)→(c ,b , a)
Генерация всех подмножеств
Пожалуй следующая задача по актуальности, это задача генерации всех подмножеств некоторого конечного множества. Эта задача также возникает при решении задач с полным перебором, только иного вида.
Посмотрим на примере, как это можно сделать. Пусть дано множество X ={a ,b ,c} . Выпишем все его подмножества, соблюдая некоторую последовательность: {a} , {b} , {c} ,
{a ,b} , {a ,c } , {b , c} , {a ,b ,c} . Несложно уловить идею этого алгоритма:
–сначала генерируем одноэлементные подмножества;
–затем дополняем полученные подмножества последующими элементами исходного множества;
–повторяем этот процесс до тех пор, пока не сможем больше ничего добавлять (при этом получим исходное множество).
Применим этот алгоритм к нашему примеру ещё раз:
{}→{a}, {b}, {c}
{a}→{a ,b}, {a ,c} {b}→{b , a}, {b , c} {c}→{c ,a}, {c ,b} {a ,b}→{a ,b ,c} {a , c}→{a ,c ,b} {b ,c}→{b ,c ,a }
Из примера хорошо видно, что у этого алгоритма большой недостаток: он генерирует одинаковые множества. Таким образом нужен более хитроумный алгоритм. Один из них заключается в том, что каждому подмножеству Y множества X ={x1, x2, …, xn} ставится в соответствие кортеж (b1, b2,... ,bn) , где
bi={1,0, xxii YY .
Тогда для нашего примера получим следующее соответствие:
→(0,0,0)
{a }→(0,0,1) {b}→(0,1,0) {c}→(1,0,0) {a ,b}→(0,1,1) {a ,c}→(1,0,1) {b ,c}→(1,1,0) {a ,b ,c}→(1,1,1)
Комбинаторная теория |
21 |
Из примера хорошо видно, что мы установили связь между всеми подмножествами конечного множества мощности n и n-разрядными двоичными числами. Таким образом генерирование всех подмножеств множества мощности n можно свести к генерированию всех n-разрядных двоичных чисел. Последняя задача может быть легко решена следующим образом. Возьмём в качестве первого двоичного числа число 02 . Тогда следующее за ним
числа получаются прибавлением единицы (инкрементированием): 12 , 102 , 112 , 1002 , …,
11...12 .
В некоторых задачах может потребоваться, чтобы последовательно генерируемые подмножества отличались друг от друга не более чем на один элемент. Вышеприведённый алгоритм этого не обеспечивает, так как, например, за 112 следует 1002 , и мы получаем совсем другое подмножество. Эту проблему можно решать, если подмножествам ставить в соответствие не обычные двоичные числа, а числа в коде Грея. Для кода Грея как раз и характерно то, что два соседних двоичных числа отличаются друг от друга не более чем на один разряд. Для генерирования последовательности чисел в коде Грея можно использовать следующий алгоритм (B – двоичное число и G – его код Грея):
–начнём с B=0 ;
–положим G[1]=B[1] ;
–G [i ]=B [i]xor B[i−1], 2≤i≤n .
Втаблице ниже приведено соответствие между обычными трёхразрядными двоичными числами и числами в коде Грея (D обозначает десятичное число):
D |
B |
G |
D |
B |
G |
|
|
|
|
|
|
0 |
000 |
000 |
4 |
100 |
110 |
|
|
|
|
|
|
1 |
001 |
001 |
5 |
101 |
111 |
|
|
|
|
|
|
2 |
010 |
011 |
6 |
110 |
101 |
|
|
|
|
|
|
3 |
011 |
010 |
7 |
111 |
100 |
|
|
|
|
|
|
Генерация всех размещений с повторениями
Рассмотрим генерацию размещений с повторениями на примере множества X ={1,2, 3} :
(1,1),(1,2),(1,3)
(2,1),(2,2),(2,3) (3,1),(3,2),(3,3)
Неправда ли, знакомая картина? Для размещений по два и по три можно использовать вложенные циклы, а для большего количества элементов в размещении можно воспользоваться рекурсией:
Decart:
Вход: X – массив с n элементами, представляющий исходное множество; D – массив с k элементами, представляющий искомый кортеж; r – текущая обрабатываемая координата в кортеже D.
Начало:
Если r == k + 1 То
// что-то делаем с кортежем D
Иначе