ДИСКРЕТНАЯ МАТЕМАТИКА (1). В. А. Ломазов р рязанов, Ю. Д. Дискретная математика учеб пособие. Ю. Д. Рязанов е изд, доп. Белгород Издво бгту, 2016. 298 с
 Скачать 4.33 Mb.
|
|
2.5. Размещения Размещением элементного множества по k местам называется расположенные в определенном порядке элементы элементного подмножества элементного множества. Количество мест не превышает количества элементов в множестве. Теорема 2.3. Количество всех различных размещений элементного множества М по k местам определяется формулой Доказательство Размещение можно представить последовательностью из k мест. Для того чтобы получить одно размещение, нужно выполнить одно за другим k действий заполнить е место в последовательности, е место итак до го места. Для выполнения го действия заполнения го места) можно взять любой элемент из множества Ми поставить его на е место, те. его можно выполнить способами, и после этого в множестве М останется n – 1 элемент. Для выполнения го действия (заполнения го места) можно взять любой элемент из оставшихся в множестве Ми поставить его на е место, те. его можно выполнить n – способами, и после этого в множестве М останется n – 2 элемента итак далее до го места. По правилу произведения все k действий могут быть выполнены )! ( ! ) 1 ( ) 2 ( ) 1 ( k n n k n n n n способами,следова- тельно, количество всех различных размещений элементного множества М по k местам равно Получить все размещения элементного множества М по k местам можно, используя метод поиска с возвращением, выполняя действия, описанные в доказательстве теоремы 2.3. Формирование го элемента размещения опишем рекурсивным алгоритмом 2.3, блок-схема которого представлена на рис. В цикле перебираются элементы множества М, которые можно поставить на е место. Если заполнено е место, то размещение сформировано и выводим его, иначе заполняем следующее i + е место по алгоритму 2.3 элементами множества М, за исключением элемента, поставленного на е место. 68 Алгоритм 2.3 порождения размещений элементного множества по k местам. Вход М — множество, элементы которого можно поставить на е место заполняемое место в последовательности Р. Выход последовательность всех размещений элементного множества по k местам. Глобальные параметры А — формируемое размещение k — количество мест. + Рис. Рекурсивный алгоритм порождения размещений элементного множества по k местам Пусть задано множество {1,2,3,4} и требуется получить все его размещения по двум местам. Схема получения всех размещений по алгоритму представлена на рис. В исходной ситуации все места размещения неопределены. В схеме к стрелкам приписаны номера действий, которые выполняются последовательно в порядке нумерации. Действия и 13 заполняют первое место размещения, действия 2, 3, 4, 6, 7, 8, 10, 11, 12, 14, 15 и 16 — второе (последнее) место размещения. Размещение ММ Конец Размещение (М) A 69 множество {3,4} размещение 2 (1,2) множество множество {2,3,4} 3 {2,4} размещение размещение (1,?) (1,3) 4 множество {3,4} размещение (1,4) 1 множество {3,4} размещение 6 (2,1) множество множество {1,3,4} 7 {1,4} размещение размещение (2,?) (2,3) 8 5 множество {1,3} множество размещение {1,2,3,4} (2,4) размещение (?,?) множество 9 {2,4} размещение 10 (3,1) множество множество {1,2,4} 11 {1,4} размещение размещение (3,?) (3,2) 13 12 множество {1,2} размещение (3,4) множество {2,3} размещение 14 (4,1) множество множество {1,2,3} 15 {1,3} размещение размещение (4,?) (4,2) 16 множество {1,2} размещение (4,3) Рис. Схема получения всех размещений по алгоритму 2.3 70 2.6. Размещения с повторениями Размещением с повторениями элементного множества по k местам называется элементная последовательность, состоящая из элементов элементного множества М, причем элементы в последовательности могут повторяться. Количество мест может превышать количество элементов в множестве. Теорема 2.4. Количество всех различных размещений с повторениями элементного множества М по k местам равно Доказательство Для того чтобы получить одно размещение с повторениями, нужно выполнить одно за другим k действий заполнить е место в последовательности, е место итак до го места. Для выполнения каждого действия можно взять любой элемент из множества Ми поставить его на соответствующее место, те. каждое из k действий можно выполнить n способами. По правилу произведения все k действий могут быть выполнены n n … n = n k способами,следовательно, количество всех различных размещений с повторениями элементного множества по k местам равно Получить все размещения с повторениями элементного множества М по k местам можно, используя метод поиска с возвращением, выполняя действия, описанные в доказательстве теоремы 2.4. Формирование го элемента размещения с повторениями опишем рекурсивным алгоритмом, блок-схема которого представлена на рис. В цикле перебираются элементы множества М (каждый элемент можно поставить на е место. Если заполнено е место, то размещение с повторениями сформировано и выводим его, иначе заполняем следующее i + е место по алгоритму 2.4 элементами множества М. Алгоритм 2.4 порождения размещений с повторениями элементного множества по k местам. Вход i — заполняемое место в последовательности R. Выход последовательность всех размещений с повторениями элементного множества М по k местам. Глобальные параметры М — элементное множество R — формируемое размещение с повторениями k — количество мест. 71 + Рис. Рекурсивный алгоритм порождения размещений с повторениями элементного множества по k местам Пусть задано множество {1,2,3} и требуется получить все его размещения с повторениями по двум местам. Схема получения всех раз- мещений по алгоритму 2.4 представлена на рис. В этой схеме представлены формируемые размещения. В каждой ситуации на очередное место в размещении можно поставить любой элемент из заданного множества {1,2,3}. В исходной ситуации все места размещения неопределенны и любой элемент множества {1,2,3} можно поставить напер- вое место. В схеме к стрелкам приписаны номера действий. В результате выполнения действия 1 на первое место размещения устанавливается элемент 1. После выполнения действия 2 на второе место размещения также устанавливается элемент 1 и первое размещение (1,1) сформировано. Затем выполняется шаг назад и действие 3 ставит элемент 2 на второе место и второе размещение (1,2) сформировано. Далее выполняется шаг назад и действие 4 заканчивает формирование очередного размещения. После этого выполняется два шага назад. Аналогичным образом формируются все остальные размещения. Действия 1, 5 и 9 заполняют первое место размещения, действия 2, 3, 4, 6, 7, 8, 10, 11 и 12 — второе место. Размещение с повторениями (i) М R i := x Конец Размещение с повторениями размещение (1,1) 2 размещение 3 размещение (1,?) (1,2) 4 размещение (1,3) 1 размещение (2,1) 6 размещение 5 размещение 7 размещение (?,?) (2,?) (2,2) 8 размещение (2,3) 9 размещение (3,1) 10 размещение 11 размещение (1,?) (3,2) 12 размещение (3,3) Рис. Схема получения всех размещений с повторениями по алгоритму 2.4 73 2.7. Сочетания Сочетанием из n элементов по k называется элементное подмножество элементного множества. Теорема 2.5. Количество всех различных сочетаний из n элементов по k определяется формулой ! )! ( ! k k n n C k n . Доказательство Можно получить все k n A размещений, упорядочив всеми возможными способами каждое из k n C сочетаний. Количество способов упорядочивания одного сочетания равно k!, следовательно, k n A = k n C k! . Отсюда ! )! ( ! ! / k k n n k A C k n k n . Пусть элементами множества М являются натуральные числа от 1 до n. Для сокращения записи такое множество будем обозначать {1..n}. Рассмотрим алгоритм порождения сочетаний в возрастающем лексикографическом порядке, те. в порядке, когда в каждом сочетании элементы расположены в порядке возрастания слева направо, а каждое следующее сочетание больше предыдущего (при сравнении одно сочетание рассматриваем как число. Например, сочетания из шести элементов потри, в возрастающем лексикографическом порядке запишутся следующим образом 123 135 234 256 124 136 235 345 125 145 236 346 126 146 245 356 134 156 246 456 Сочетания в лексикографическом порядке можно порождать, используя метод поиска с возвращением. Начиная с го места будем последовательно формировать элементы сочетания С. На первое место в сочетании можно ставить элементы из множества {1..n – k + 1}. Формирование го элемента сочетания опишем рекурсивным алгоритмом 2.5, блок-схема которого представлена на рис. В цикле перебираются элементы множества {b..n – k + i}, которые можно поставить на е место. Если на е место поставлен элемент x, то минимальный элемент, который можно поставить на i + е место, равен x + 1. Если заполнено е место, то сочетание сформировано и выводим его, иначе заполняем следующее i + е место по алгоритму 2.5. 74 Алгоритм 2.5 порождения сочетаний из n элементов по k. Вход i — заполняемое место в сочетании С b — минимальный элемент, который можно поставить на е место. Выход последовательность всех сочетаний из n элементов по k ввоз- растающем лексикографическом порядке. Глобальные параметры С — формируемое сочетание k — количество элементов в сочетании. + Рис. Рекурсивный алгоритм порождения сочетаний из n элементов по Пусть задано множество {1,2,3,4,5} и требуется получить все его сочетания по 3. Схема получения всех сочетаний по алгоритму 2.5 представлена на рис. В этой схеме представлены формируемые сочетания и множества, элементы которых можно поставить на очередное место в сочетании. В исходной ситуации все места сочетания неопределенны и на первое место можно поставить любой элемент множества {1,2,3}. В схеме к стрелкам приписаны номера действий. В результате Сочетание (i, b) x {b..n-k+i} C i := x Конец Сочетание (i+1, x+1) С 75 выполнения действия 1 на первое место сочетания устанавливается элемента на второе место после этого можно поставить любой элемент множества {2,3,4}. После выполнения действия 2 на второе место сочетания устанавливается элемента на третье место после этого можно поставить любой элемент множества {3,4,5} (действие 3) и первое сочетание сформировано. Затем выполняется шаг назад и действие 4, ставящее элемент 4 из множества {3,4,5} на третье место и второе сочетание сформировано. Аналогичным образом формируются все остальные сочетания. Действия 1, 11 и 17 заполняют первое место сочетания, действия 2, 6, 9, 12, 15 и 18 — второе место, действия 3, 4, 5, 7, 8, 10, 13, 14, 16 и 19 — третье место. сочетание 3 {1,2,3) множество {3,4,5} 4 сочетание сочетание {1,2,4) {1,2,?} 5 2 сочетание {1,2,5) множество множество 7 сочетание {2,3,4} 6 {4,5} {1,3,4) сочетание сочетание 8 {1,?,?} {1,3,?} сочетание 9 {1,3,5) 1 множество {5} 10 сочетание сочетание {1,4,5) множество {1,4,?} {1,2,3} сочетание 11 множество 13 сочетание {?,?,?} 12 {4,5} {2,3,4) множество сочетание 14 {3,4} {2,3,?} сочетание сочетание 15 {2,3,5) 17 {2,?,?} множество {5} 16 сочетание сочетание {2,4,5) {2,4,?} множество множество {4} 18 {5} 19 сочетание сочетание сочетание {3,4,5) {3,?,?} {3,4,?} Рис. Схема получения всех сочетаний по алгоритму 2.5 76 2.8. Перестановки с повторениями Множество, которое может содержать одинаковые элементы, называется мультимножеством Например М = {1,1,2,3,1,2,3} — мультимножество, которое содержит элементы 1, 2 и 3, причем элемент 1 входит в мультимножество 3 раза, а элементы 2 и 3 — по 2 раза. Мультимножества равны, если они состоят из одних и тех же элементов, поэтому {1,1,2,3,1,2,3} = {1,1,1,2,2,3,3}, те. порядок расположения элементов неважен. Мультимножество, состоящее из конечного числа элементов, называется конечным. Количество элементов в мультимножестве S называется мощностью мультимножества и обозначается |S|. Мощность мультимножества М = {1,1,2,3,1,2,3} равна семи, |M| = Количество n i вхождений элемента s i в мультимножество S называется кратностью элемента Конечное мультимножество S будем записывать в следующем виде Здесь все s i различны и n i – кратность элемента s i . Тогда мощность S равна k i i n S 1 . Учитывая введенное обозначение, мультимножество М = {1,1,2,3,1,2,3} можно записать так {3*1,2*2,2*3}. Перестановкой с повторениями называется расположенные в определенном порядке элементы мультимножества. Теорема 2.6. Число перестановок с повторениями для мультимножества выражается формулой ! ! ! ! ) ,..., , ( 2 1 2 1 k k n n n n n n n n P , где Доказательство Рассмотрим одну перестановку мультимножества и заменим в ней все одинаковые элементы разными. Тогда, число различных перестановок, которые можно составить из рассматриваемой, равно n 1 ! n 2 ! … n k !. Проделав это для каждой перестановки, получим n! перестановок. Следовательно, P n (n 1 ,n 2 ,…,n k ) n 1 ! n 2 ! … n k ! = n!. Отсюда ! ! ! ! ) ,..., , ( 2 1 2 1 k k n n n n n n n n P S={ s 1 ,...,s 1 , s 2 ,...,s 2 , ... , s k ,...,s k }={n 1 *s 1 ,n 2 *s 2 ,...,n k *s k }. n 1 -раз n 2 -раз n k -раз 77 Алгоритм 2.6 (рис) порождения всех перестановок с повторениями практически не отличается от алгоритма 2.2 порождения всех перестановок множества, за исключением того, что в алгоритме 2.6 обрабатывается мультимножество. Определим мультимножество С, являющееся результатом разности мультимножеств Аи В (С = А – В. Если элемент универсума не принадлежит мультимножеству, то будем считать, что его кратность равна нулю. Элемент x C, если кратность А элемента x в мультимножестве А больше кратности В элемента x в мультимножестве В и кратность k С элемента x в мультимножестве С определяется по формуле k C = k A – Алгоритм 2.6 порождения перестановок с повторениями. Вход М — мультимножество, элементы которого можно поставить на е место i — заполняемое место в последовательности Р. Выход последовательность всех перестановок с повторениями. Глобальные параметры Р — формируемая перестановка с повторениями мощность мультимножества. + Рис. Рекурсивный алгоритм порождения перестановок с повторениями Перестановка ММ Р := x Конец Перестановка (М) Р 78 Пусть задано мультимножество {1,1,2,2}={2*1,2*2} и требуется получить все перестановки с повторениями. Это мультимножество содержит элементы 1 и 2 кратности 2. Схема получения всех перестановок по алгоритму 2.6 представлена на рис. В этой схеме формируемые перестановки заключены в круглые скобки, а мультимножества, элементы которых можно поставить на очередное место в перестановке – в фигурные. В исходной ситуации все места перестановки неопределенны и на первое место можно поставить любой элемент мультимножества 1 или 2. В схеме к стрелкам приписаны номера действий. В результате выполнения действия 1 на первое место перестановки устанавливается элемента на второе место после этого можно поставить любой элемент мультимножества {1,2,2}. После выполнения действия 2 на второе место перестановки устанавливается элемента на третье место после этого можно поставить любой элемент мультимножества {2,2}. После выполнения действий 3 и 4 первая перестановка {1,1,2,2} сформирована. Затем выполняется 3 шага назад и действие 5, ставящее второй элемент из мультимножества {1,2,2} на третье место, после чего на четвертое место можно поставить любой элемент из мультимножества {1,2}. Далее, после последовательного выполнения действий 6 и 7 вторая перестановка сформирована. Аналогичным образом формируются все остальные перестановки. {1,1,2,2} (?,?,?,?) 1 10 {1,2,2} {1,1,2} (1,?,?,?) (2,?,?,?) 2 5 11 16 {2,2} {1,2} {1,2} {1,1} (1,1,?,?) (1,2,?,?) (2,1,?,?) (2,2,?,?) 3 6 8 12 14 17 {2} {2} {1} {2} {1} {1} (1,1,2,?) (1,2,1,?) (1,2,2,?) (2,1,1,?) (2,1,2,?) (2,2,1,?) 4 7 9 13 15 18 (1,1,2,2) (1,2,1,2) (1,2,2,1) (2,1,1,2) (2,1,2,1) (2,2,1,1) Рис. Схема получения всех перестановок с повторениями по алгоритму 2.6 |