ДИСКРЕТНАЯ МАТЕМАТИКА (1). В. А. Ломазов р рязанов, Ю. Д. Дискретная математика учеб пособие. Ю. Д. Рязанов е изд, доп. Белгород Издво бгту, 2016. 298 с
 Скачать 4.33 Mb.
|
|
2.10.4. Все упорядоченные разбиения множества Рассмотрим все упорядоченные разбиения множества M. Теорема 2.12. Количество всех различных упорядоченных разбиений элементного множества М определяется формулой m i ki i i n k n n n n n R 1 2 1 1 ! ! ! ! , где 1 1 k n C m , (n 1i ,n 2i ,…,n ki ) — я композиция числа n из k частейс ограничением Конец Композиция (i+1, S+x) C Композиция (i, S) C k :=n–(S+x) 89 Доказательство элементное множество можно разбить на 1 подмножество, на 2 подмножества итак далее, на n подмножеств, те. количество k непустых подмножеств, на которые можно разбить элементное множество, может быть от 1 до n, отсюда количество всех различных упорядоченных разбиений элементного множества М определяется формулой m i ki i i n k n n n n n R 1 2 1 1 ! ! ! ! , где 1 1 k n C m , (n 1i ,n 2i ,…,n ki ) — я композиция числа n из k частейс ограничением. Для порождения всех упорядоченных разбиений элементного множества М достаточно, перебирая все k в диапазоне от 1 до n, получать все композиции числа n из k частей с ограничением n i > 0, используя алгоритм 2.8, и к каждой композиции (n 1 ,n 2 ,…, n k ) применить алгоритм порождения перестановок с повторениями мультимножества {n 1 *1,n 2 *2,…, n k *k}, в котором перестановки с повторениями интерпретировать как разбиения. 2.11. Разбиения множества Разбиением множества М называется множество из непустых, попарно непересекающихся подмножеств множества М, объединение которых дает множество М. Разбиения множества M на k подмножеств с мощностями {n 1 ,n 2 ,…,n k } Рассмотрим разбиения элементного множества M на k подмножеств с мощностями {n 1 ,n 2 ,…,n k }, где {n 1 ,n 2 ,…,n k } — мультимножество. Одно такое разбиение представляет собой множество {М 1 ,М 2 ,…,М k } подмножеств множества М, таких, что |M 1 | = n 1 , |M 2 | = n 2 ,…, |M k | = n k и n 1 + n 2 +…+ n k = n. Среди подмножеств в разбиении {М 1 ,М 2 ,…,М k } можно выделить l 1 подмножеств мощности 1, l 2 подмножеств мощности 2 итак далее, l n подмножеств мощности n, при этом 1 l 1 + 2 l 2 + … + n l n = n. Теорема 2.13. Количество всех различных разбиений элементного множества М на k подмножеств с мощностями {n 1 ,n 2 ,…,n k } определяется формулой ! ! ! ) ! ( ) ! 2 ( ) ! 1 ( ! ) ,..., , ( 2 1 2 1 2 Ф Доказательство. Каждое разбиение элементного множества M на k подмножеств с мощностями можно упорядочить k! способами и получить все упорядоченные разбиения элементного множества М на k подмножеств с мощностями {n 1 ,n 2 ,…, n k } , число которых определяется формулой ! ! ! ! ) ! ( ) ! 2 ( ) ! 1 ( ! } ,..., , { 2 1 2 1 2 1 n l l l k n l l l k n n n n n P n , следовательно, количество всех различных разбиений элементного множества М на k подмножеств с мощностями определяется формулой ! ! ! ) ! ( ) ! 2 ( ) ! 1 ( ! ! } ,..., , { ) ,..., , ( 2 1 2 1 2 1 2 Ф Рассмотрим алгоритм порождения разбиений элементного множества М на k подмножеств с мощностями {n 1 ,n 2 ,…,n k }. Обозначим R i – некоторое разбиение элементного множества {1..i}, а R n – любое разбиение элементного множества М на k подмножеств с мощностями {n 1 ,n 2 ,…, n k }. Будем последовательно получать разбиения R 1 ,R 2 ,…,R i ,…,R n , не противоречащие разбиениям R n , те. R i такое, что из него путем добавления элементов в его подмножества или добавления подмножеств можно получить разбиение Если сформировано разбиение R i-1 множества {1..i – 1} на p подмножеств, то из него можно получить разбиения R i , добавляя элемент i сначала в первое, затем во второе итак далее, в е подмножество разбиения или добавляя новое, p + е одноэлементное подмножество {i}. Ноне из каждого, сформированного таким образом, разбиения R i можно будет получить разбиения Для определения возможности получения из разбиения R i разбиений R n введем характеристику H(R i ) разбиения R i . Эта характеристика представляет собой элементную, упорядоченную по неубыванию, последовательность мощностей подмножеств разбиения R i . Если количество подмножеств в разбиении R i меньше k, то характеристика H(R i ) будет содержать нулевые элементы. Разбиение R i можно задать разрядным вектором S, в котором S j – номер подмножества, которому принадлежит элемент j. Пример разбиений и их характеристик приведен в табл. 2.2. Введенную характеристику разбиения используем следующим образом. Если H(R i ) H(R n ) ( H(R i ) H(R n ) истинно, если каждый элемент H(R i ) не больше соответствующего элемента из H(R n ) ), то из разбиения R i можно получить разбиение. Например, если H(R n ) = (1,2,2), то, анализируя характеристики (см. табл, видим, что из го разбиения {{1,2,3}}, го разбиения 91 {{1,2,4},{3}} иго разбиения {{1,3,4},{2}} нельзя получить разбиения элементного множества на 3 подмножества с мощностями {1,2,2}, а из всех остальных — можно. Таблица 2.2 Характеристики разбиений № п/п Разбиение R Вектор S Характеристика H(R) 1 {1} 1 001 2 {1,2} 11 002 3 {1},{2} 12 011 4 {1,2,3} 111 003 5 {1,2},{3} 112 012 6 {1,3},{2} 121 012 7 {1},{2,3} 122 012 8 {1},{2},{3} 123 111 9 {1,2,4},{3} 1121 013 10 {1,2},{3,4} 1122 022 11 {1,2},{3},{4} 1123 112 12 {1,3,4},{2} 1211 013 13 {1,3},{2,4} 1212 022 14 {1,3},{2},{4} 1213 112 В алгоритме порождения разбиений разбиения представлены вектором. Формирование го разряда вектора S соответствует определению подмножества разбиения, в которое добавляется элемент i. Если разбиение содержит p подмножеств, то элемент i можно включить в подмножество с номером x от 1 до p + 1, если p + 1 k, или до k, в противном случае, что соответствует записи в й разряд значения x, но при этом должно соблюдаться условие H(R i ) H(R n ). Если i = n, то разбиение получено, иначе поэтому же алгоритму формируем i + й разряд вектора S (разбиение R i+1 ). При рекурсивном обращении передаем количество подмножеств в сформированном разбиении R i . Припер- вом обращении передаем I = 1 для формирования го разряда вектора S и p = 0, означающее пустоту начального разбиения. Схема формирования векторов S, соответствующих разбиениям множества M={1,2,3,4,5} натри подмножества с мощностями {1,2,2}, показана на риса блок-схема алгоритма 2.9 порождения разбиений элементного множества М на k подмножеств с мощностями {n 1 ,n 2 ,…, n k } — на рис. 92 1122 11223 112 1123 11232 11 11233 1 1212 12123 12 121 1213 12132 12133 122 1221 12213 1223 12231 12233 123 1231 12312 12313 1232 12321 12323 1233 12331 12332 Рис. Схема формирования векторов S 93 Алгоритм 2.9 порождения разбиений элементного множества М на k подмножеств с мощностями {n 1 ,n 2 ,…,n k }. Вход i — заполняемое место в векторе S; p — количество подмножеств в разбиении Выход последовательность всех векторов S, задающих разбиения. Глобальные параметры S — формируемый вектор n — мощность множества k — количество подмножеств в разбиении. + Рис. Рекурсивный алгоритм порождения разбиений элементного множества М на k подмножеств с мощностями {n 1 ,n 2 ,…,n k }. 2.11.2. Все разбиения множества M на k подмножеств Рассмотрим все разбиения элементного множества M на k подмножеств. Теорема 2.14. Количество всех различных разбиений элементного множества М на k подмножеств определяется формулой Ф 2 1 ! ! ! ! ! 1 ) ( , Разбиение (i, p) x {1..min(p+1,k)} и H(R i ) H(R n ) S i := x Конец Разбиение (i+1, max(x,p)) S 94 где 1 1 k n C m , (n 1i ,n 2i ,…,n ki ) — я композиция числа n из k частейс ограничением. Доказательство. Каждое разбиение элементного множества M на k подмножеств можно упорядочить k! способами и получить все упорядоченные разбиения элементного множества М на k подмножеств, число которых определяется формулой m i ki i i n n n n n k P 1 2 1 ! ! ! ! ) ( , где 1 1 k n C m , (n 1i ,n 2i ,…,n ki ) — я композиция числа n из k частейс ограничением. Следовательно, количество всех различных разбиений элементного множества М на k подмножеств определяется формулой Ф 2 1 ! ! ! ! ! 1 ! ) ( ) ( , где 1 1 k n C m , (n 1i ,n 2i ,…,n ki ) — я композиция числа n из k частейс ограничением. Для порождения всех разбиений элементного множества на k подмножеств можно получить все такие мультимножества {n 1 ,n 2 ,…,n k }, что n 1 + n 2 +…+ n k = n, и, считая, что n 1 ,n 2 ,…,n k – мощности подмножеств в разбиении, применить к каждому из них алгоритм 2.9 порождения разбиений элементного множества на k подмножеств с мощностями. Мультимножество {n 1 ,n 2 ,…,n k }, состоящее из натуральных чисел, такое, что n 1 + n 2 +…+ n k = n, называется разбиением числа n на k частей. Последовательность всех разбиений числа n на k частей можно записать в неубывающем лексикографическом порядке, например, все разбиения числа 8 на 4 части запишутся следующим образом 1115 1124 1133 1223 2222 Для порождения разбиений числа n из k можно использовать метод поиска с возвращением. Начиная с го места, будем последовательно формировать элементы разбиения R. Формирование го элемента разбиения опишем рекурсивным алгоритмом 2.10, блок-схема которого представлена на рис. В цикле перебираются элементы множества, которые можно поставить на е место. Минимальный элемент, который можно поставить на первое место, равен 1. Минимальный элемент, который можно поставить на очередное е место при 1 < i < k, равен элементу, поставленному на i – е место, а максимальный — такой, что сумма сформированных i – 1 элементов плюс сумма минимальных значений, которые можно поставить на оставшиеся места разбиения, не превышает числа n, те. [(n – S) / (k – i + 1)], где S — сумма сформированных элементов, k – i + 1 – количество оставшихся мест. На последнее, е место разбиения можно поставить только n – (S + x), где х — элемент, поставленный на k – е место, S + x — сумма k – 1 элементов разбиения. Если заполнено k – е место, то однозначно заполняем последнее место, как описано выше, и выводим разбиение, иначе заполняем следующее i + е место по алгоритму 2.10. Алгоритм 2.10 порождения разбиений числа n из k частей. Вход i — заполняемое место в разбиении b — минимальное число, которое можно поставить на е место S — сумма первых i – 1 элементов разбиения. Выход последовательность всехразбиений числа n из k частей. Глобальные параметры R — формируемое разбиение n — исходное число k — количество элементов в разбиении. + Рис. Рекурсивный алгоритм порождения разбиений числа n из k частей x {b..[(n–S)/(k–i+1)]} R i := x i=k–1 Конец Разбиение (i+1,x,S+x) R Разбиение (i,b,S) R k :=n–(S+x) 96 Схема получения всех разбиений числа 8 на 4 части по алгоритму 2.10 представлена на рис. В исходной ситуации все места разбиения неопределенны и на первое место можно поставить числа от 1 до [( n – S) / (k – i + 1)] = [(8 – 0) / (4 – 1 + 1)] = 2. В схеме к стрелкам приписаны номера действий. В результате выполнения действия 1 напер- вое место разбиения устанавливается число 1, на второе место после этого можно ставить числа от 1 до [(n – S) / (k – i + 1)] = [(8 – 1) / (4 – 2 + + 1)] = 2. После выполнения действия 2 на второе место разбиения устанавливается число 1, а на третье место после этого можно поставить числа от 1 до [(n – S) / (k – i + 1)] = [(8 – 2) / (4 – 3 + 1)] = 3. После выполнения действия 3 на третье место разбиения устанавливается число 1 и действием 4 остается установить n – (S + x) = 8 – (2 + 1) = 5 на четвертое место (х = 1 – число на третьем месте. Первое разбиение {1,1,1,5} получено. Затем выполняется 2 шага назад и действие 5, ставящее число 2 на третье место разбиения, после чего на четвертое место остается установить число n – (S + x) = 8 – (2 + 2) = 4 действием 6. Второе разбиение {1,1,2,4} получено. Аналогичным образом формируются все остальные разбиения. множество {1,2} разбиение {?,?,?,?} 1 12 множество множество {1,2} {2} разбиение разбиение {1,?,?,?} {2,?,?,?} 2 9 13 множество множество множество {1,2,3} {2} {2} разбиение разбиение разбиение {1,1,?,?} {1,2,?,?} {2,2,?,?} 3 4 7 10 14 множество множество множество множество множество {5} {4} {3} {3} {2} разбиение разбиение разбиение разбиение разбиение {1,1,1,?} {1,1,2,?} {1,1,3,?} {1,2,2,?} {2,2,2,?} 4 6 8 11 15 разбиение разбиение разбиение разбиение разбиение {1,1,1,5} {1,1,2,4} {1,1,3,3} {1,2,2,3} {2,2,2,2} Рис. Схема получения всех разбиений числа 8 на 4 части 97 Рассмотрим еще один алгоритм порождения всех разбиений элементного множества на k подмножеств, построенный на основе метода поиска с возвращением, не использующий другие алгоритмы. Также, как ив алгоритме порождения разбиений элементного множества на k подмножеств с мощностями {n 1 ,n 2 ,…,n k }, будем последовательно получать разбиения R 1 ,R 2 ,…,R i ,…,R n , не противоречащие разбиениям R n , где R n — разбиение элементного множества на k непустых подмножеств без ограничения на мощности подмножеств, те. такое, что из него, путем добавления элементов в его подмножества или добавления подмножеств, можно получить разбиение Если сформировано разбиение R i-1 множества {1..i – 1} на p подмножеств, то из него можно получить разбиения R i , добавляя элемент i сначала в первое, затем во второе итак далее, в е подмножество разбиения или добавляя новое, p + е одноэлементное подмножество {i}. Ноне из каждого, сформированного таким образом, разбиения R i можно будет получить разбиения R n Во-первых, в разбиении R n должно быть ровно k подмножеств, поэтому, если разбиение R i-1 содержит p = k подмножеств, тоновое+ е подмножество в разбиении R i создавать нельзя. Далее, если разбиение содержит p подмножеств, то будем говорить, что i – 1 элемент элементного множества распределен по p подмножествам разбиения и остаются нераспределенными n – (i – 1) элементов, при этом остаются несформированными k - p подмножеств. Если количество нераспределенных элементов n – (i – 1) больше количества k – p подмножеств, которые еще необходимо сформировать, то элемент i можно добавить в любое подмножество разбиения R i-1 , иначе, для получения разбиения R i , в разбиение R i-1 можно только добавить новое, p + е, подмножество {i}. Для хранения разбиения используется вектор S, в котором S i — номер подмножества, которому принадлежит элемент i. Формирование го разряда вектора S соответствует определению подмножества разбиения, в которое добавляется элемент i. Если разбиение R i-1 содержит p подмножеств, то элемент i можно включить в подмножество, минимальный номер которого равен 1, если n – (i – 1) > k – p, или p + 1 — в противном случае, а максимальный номер — p + 1, если p + 1 k, или k — в противном случае. Если i = n, то разбиение получено, иначе поэтому же алгоритму формируем i + й разряд вектора S (разбиение R i+1 ). При рекурсивном обращении передаем количество max(x,p) подмножеств в сформированном разбиении R i . При первом обращении передаем для формирования го разряда вектора S и p = 0, означающее пустоту начального разбиения. 98 Блок-схема алгоритма 2.11 порождения всех разбиений элементного множества М на k подмножеств представлена на риса схемы формирования разбиений множества M={1,2,3,4} натри подмножества и соответствующих им векторов S показаны на рис. Алгоритм 2.11 порождения всех разбиений элементного множества М на k подмножеств. Вход i — заполняемое место в векторе S; p — количество подмножеств в разбиении Выход последовательность всех векторов S, задающих разбиения. Глобальные параметры S — формируемый вектор n — мощность множества k — количество подмножеств в разбиении. + Рис. Рекурсивный алгоритм порождения всех разбиений элементного множества М на k подмножеств Разбиение (i,p) x {b..min(p+1,k)} S i := x Конец Разбиение (i+1,max(x,p)) S b:= 1, если n–(i–1)>k–p p+1, иначе 99 а {{1,2},{3}} {{1,2},{3},{4}} {1,2} {1} {{1,3},{2}} {{1,3},{2},{4}} {1},{2} {{1},{2,3}} {{1},{2,3},{4}} {{1,4},{2},{3}} {{1},{2},{3}} {{1},{2,4},{3}} {{1},{2},{3,4}} б 1,1,2,? 1,1,2,3 1,1,?,? 1,?,?,? 1,2,1,? 1,2,1,3 1,2,?,? 1,2,2,? 1,2,2,3 1,2,3,1 1,2,3,? 1,2,3,2 1,2,3,3 Рис. Схемы формирования разбиений и соответствующих им векторов S: а — схема формирования разбиений б — схема формирования векторов S 100 |