Информатика

Комбинаторика в информатике

13.5.2022

9837

На этой странице вы узнаете

Стоит ли искать пароль от кодового замка?
Как создать самую красивую гирлянду?
Как работают безопасные пароли?

Комбинаторика — это увлекательная наука, которая помогает нам понять, как много комбинаций можно создать из заданных элементов. Она находит применение в самых разных сферах жизни: от математики и физики до бизнеса и игр.

Например, вы когда-нибудь задумывались над тем, что общего у автомобильного номера, карточной игры и расписания школьных занятий? Как найти количество всевозможных паролей в кодовом замке? Если вы хотите узнать больше о комбинаторике и ее применении в информатике, то добро пожаловать в статью!

Применение комбинаторики

Комбинаторика — это раздел математики, который занимается решением задач, связанных с выбором и расположением элементов какого-либо множества по заданным параметрам.

Мы прибегаем к помощи комбинаторики, когда речь идет о данных как о наборе последовательностей, которые состоят из определенных элементов, расположенных в определенном порядке.

Что может служить примерами таких данных?

Автомобильные номера — набор букв и цифр в определенном порядке.
Кодовый замок — набор цифр в определенном порядке.
Карточные игры — наборы карт, которые могут находиться у вас на руках.
Расписание занятий — варианты порядка проведения уроков.

Собственно, комбинаторика может помочь нам:

узнать общее количество возможных автомобильных номеров или потенциальных паролей кодового замка;
оценить шанс нахождения бубновой десятки на руках у вашего соперника;
посмотреть на другие возможные варианты расписания, которое можно было бы составить и поудобнее.

Допустим, мы забыли пароль от кодового замка. Сколько всего возможно потребуется перебрать кодов в нашем замке? Давайте перейдем к изучению теории, которая поможет найти ответ на этот вопрос.

Размещения и перестановки

Самое простое, с чем нам может помочь комбинаторика — это подсчет комбинаций элементов, от которого мы сможем отталкиваться дальше. Для удобства различают два основных вида расположения элементов в последовательностях:

Размещения — элементы набора могут использоваться в последовательности определенной длины любое количество раз (в том числе ни разу).

Пример: кодовый замок. Никто не запретит нам использовать любую цифру любое количество раз или не использовать совсем.

Перестановки — возможные последовательности образуются изменением порядка следования элементов друг за другом. Каждый элемент набора используется ровно 1 раз.

Пример: распределение 5 человек на дежурства в течение 5 дней. Было бы справедливо, если бы один человек дежурил только один раз, но вот в какой из дней — уже есть выбор.

Когда мы разобрались с основными определениями размещений и перестановок, хочется узнать, как подсчитать количество комбинаций, удовлетворяющих различным требованиям.

Подсчет количества комбинаций

Количество комбинаций зависит от вариантов расстановки элементов. Чем больше символов может стоять на каждой позиции, тем больше будет комбинаций. Полное их количество рассчитывается как произведение количества возможных символов на каждой позиции.

В размещениях каждый элемент может быть на любой позиции и может встретиться любое количество раз. То есть на каждой из k позиций может быть любой из n символов, тогда всего размещений может быть:

\(N=n^k\)

Как найти пароль от чемодана?

Иногда в личных чемоданах используют маленькие кодовые замки. Но бывает так, что заветный пароль теряется и забывается. Если замок достаточно небольшой, а чемодан любимый и единственный, то можно перебрать все варианты расположения цифр на нем. Но как же узнать, сколько их всего?

Представим следующую задачу: у нас есть замок, как на изображении ниже. То есть 3 позиции (3 вращательных элемента), тогда k = 3. А цифр всего 10 (от 0 до 9), то есть n = 10. Тогда всего размещений: N=10*10*10=1000.

Итого необходимо перебрать 1000 разных комбинаций, что достаточно много.

В перестановках последовательности отличаются только порядком следования элементов. Значит, каждый из элементов будет использоваться ровно 1 раз.

На первой позиции может стоять любой из n символов.
На второй — любой из оставшихся n − 1 символов.
На третьей — любой из еще не использовавшихся, то есть n − 2.
На самой последней позиции может использоваться только один оставшийся символ.

Поэтому количество комбинаций перестановок рассчитывается как факториал количества символов:

\(1*2* …*(n-2)*(n-1)*n=n!\), то есть произведение всех чисел от 1 до n.

Допустим, что мы захотели посмотреть, сколько слов можно составить из неповторяющихся букв П, А, Р, О, Л, Ь:

длина слова так и остается — 6 символов;
каждая буква встречается по 1 разу.

Тогда необходимо найти количество перестановок, а оно равно факториалу от количества символов, то есть факториалу от 6: 6!=720.

Как создать самую красивую гирлянду?

Детство — пора чудес! Каждый хотя бы раз в жизни делал праздничную гирлянду своими руками. Но вот незадача — у нас есть 4 флажка разного цвета и нитка, но мы не знаем, как лучше расположить флажки на ниточке. В помощь приходит комбинаторика.

Сколько всего вариантов расположения флажков на нитке?
— Флажков у нас 4. Если мы возьмем какой-то флажок, поместим его на первое место, то останется всего 3.
— Выберем один из этих трех и также поместим, но уже на второе место.
— Осталось 2 — выберем флажок на третье место, а оставшийся поместим на последнее, четвертое место.

Так мы расположили флажки одним из возможных способов. Но комбинаций может быть множество. Посчитаем их: n=4, так как всего 4 флажка. Тогда количество комбинаций: n!=4!=1*2*3*4=24.

То есть существует целых 24 комбинации для четырех флажков. Можно долго выбирать их расположение на гирлянде.

А что, если у нас есть флажки, цвета которых повторяются? Как подсчитать количество комбинаций в данном случае? Такая ситуация называется — перестановки с повторениями.

Если у нас есть всего n элементов, среди которых n1 элементов 1-го типа, \(n_2\) элементов 2-го типа, …, \(n_k\) элементов типа k, то количество перестановок с повторениями будет рассчитываться, как:

Например, у нас есть следующий набор флажков:

5 красных флажков;
2 синих флажка;
1 фиолетовый флажок;
3 зеленых флажка.

Определим, сколькими способами мы можем расположить эти флажки на нитке, чтобы сделать гирлянду. Используя формулу, выпишем все переменные:

\(n=5+2+1+3=11\) — всего флажков;
\(n_1= 5\) (красные), \(n_2=2\) (синие), \(n_3=1\) (фиолетовый), \(n_4=3\) (зеленые).

Тогда общее количество перестановок: \(11!/(5!*2!*1!*3!)= 27720\). Это и будет ответом.

Если в условиях задачи не сказано о перестановках или размещениях — составляем выражение согласно требованиям:

А. Считаем, какое количество символов может находиться на каждой позиции (учитывая ограничения, наложенные на символы).
Б. Перемножаем полученные значения.

Например, мы выбираем пароль по следующим условиям:

длина пароля — 6 символов;
используются только символы P, A, S, W, O, R, D, 1, 2, 3;
символ Р должен быть на первом месте и больше не встречаться в пароле;
символ 3 должен быть на последнем месте и больше не встречаться в пароле.

Определим, какие символы на каких позициях могут находиться:

Теперь можем составить выражение, чтобы найти количество всех возможных вариантов пароля. Перемножим количество возможных символов на каждой позиции:
\(N = 1 * 8 * 8 * 8 * 8 * 1 = 4096\).

Как работают безопасные пароли?

При регистрации на сайтах нас просят придумать пароль.
Некоторые сайты дают задачку со звездочкой:
— пароль должен быть настолько длинным, чтобы не влезал в поле для пароля;
— пароль должен содержать символы, о которых мы раньше и не слышали.

Доля разумности в этих требованиях присутствует. Использование сложного пароля создает множество возможных комбинаций знаков. Такой пароль не взломать простым перебором.

Одна фирма по кибербезопасности посчитала, что пароль длиной 11 символов, состоящий только из цифр, взламывается меньше чем за секунду. При использовании цифр, букв в разных регистрах и спецсимволов, на взлом уйдет 34 года. Если символов будет не 11, а 12, то взлом сложного пароля займет около 3000 лет.

Мы рассмотрели весь теоретический материал. Возможно, вам сейчас стало немного грустно, ведь столько чисел, столько формул, столько правил. Комбинаторика действительно требует времени и внимания, особенно в сложных и больших задачах. Но данная проблема уже решена — многие инструменты для комбинаторики есть в Python.

Размещения и перестановки в программе Python

Для облегчения расчетов в Python существует модуль itertools, который содержит следующие инструменты:

permutations(набор символов, r = длина последовательности) — создает перестановки заданной длины переданного набора.	product(набор символов, repeat = длина последовательности) — создает размещения заданной длины из заданного набора символов.
Код программы: from itertools import permutations for i in permutations(«abcd», r = 2): print(i)	Код программы: from itertools import product for i in product(«abcd», repeat = 2): print(i)
Вывод программы: (‘a’, ‘b’) (‘a’, ‘c’) (‘a’, ‘d’) (‘b’, ‘a’) (‘b’, ‘c’) (‘b’, ‘d’) (‘c’, ‘a’) (‘c’, ‘b’) (‘c’, ‘d’) (‘d’, ‘a’) (‘d’, ‘b’) (‘d’, ‘c’)	Вывод программы: (‘a’, ‘a’) (‘a’, ‘b’) (‘a’, ‘c’) (‘a’, ‘d’) (‘b’, ‘a’) (‘b’, ‘b’) (‘b’, ‘c’) (‘b’, ‘d’) (‘c’, ‘a’) (‘c’, ‘b’) (‘c’, ‘c’) (‘c’, ‘d’) (‘d’, ‘a’) (‘d’, ‘b’) (‘d’, ‘c’) (‘d’, ‘d’)

Все комбинации будут возвращены в виде списка символов.

Пример 1.

Допустим, мы будем составлять пароли длиной 6 символов из того же набора символов P, A, S, W, O, R, D, 1, 2, 3, но с дополненным условием:

Символ Р может использоваться в пароле любое количество раз, но обязательно должен быть на первом месте.
Символ 3 должен быть использован в пароле ровно 3 раза.
В пароле не должно быть сочетания 123.

Решение:

Для создания всех вариаций пароля будем использовать product модуля itertools.

from itertools import product

Создадим переменную-счетчик подходящих паролей.

cnt = 0

Все пароли будем перебирать циклом for.

for i in product(«PASWORD123», repeat = 6):

Нам нужно проверить все условия задачи. Элемент комбинации с индексом 0 равен “Р”, “3” встречается в ней ровно 3 раза, а также в списке символов комбинации не должно быть набора: 1 2 3.

if i[0] == «P» and i.count(«3″) == 3 and ‘123’ not in ».join(i):

При нахождении подходящего пароля будем увеличивать наш счетчик на 1.

cnt += 1

В конце программы выведем его значение на экран.

print(cnt)

Полный код программы:

from itertools import product

cnt = 0
for i in product(«PASWORD123», repeat = 6):
if i[0] == «P» and i.count(«3″) == 3 and ‘123’ not in ».join(i):
cnt += 1
print(cnt)

Вывод программы: 807

Пример 2.

Допустим, что мы будем составлять слова перестановкой букв слова УМСКУЛ. Необходимо найти количество таких слов, включая текущее.

Решение:

Для создания всех перестановок пароля будем использовать permutations модуля itertools.

from itertools import permutations

Создадим множество sl, в которое будем добавлять слова. Особенность множеств состоит в том, что оно хранит в себе неповторяющиеся элементы. Это поможет избежать повторов, так как Python будет считать буквы У как за две разные, в этом его особенность.

sl = set()

Все слова будем перебирать циклом for.

for i in permutations(«УМСКУЛ»):

Добавляем каждое слово в множество.

sl.add(i)

В конце программы выведем длину множества на экран.

print(len(sl))

Полный код программы:

from itertools import permutations

sl = set()
for i in permutations(«УМСКУЛ»):
sl.add(i)

print(len(sl))

Вывод программы: 360

Задачи, связанные с комбинаторикой, встречаются в задании 8 ЕГЭ. Потренируемся применять полученные навыки на примере задачи, аналогичной типовым задачам этого номера экзамена.

Василий составляет 5-буквенные слова из букв У, М, С, К, Л. Каждую букву нужно использовать ровно 1 раз. При этом слово не может начинаться с буквы У. Сколько таких слов может составить Василий?

Решение.
1. Сначала проанализируем задачу. Заметим, что данный тип слов — это слова с неповторяющимися буквами. То есть каждая буква входит в слово 1 раз, об этом сказано в условии. Поэтому мы будем использовать permutations.

from itertools import permutations

2. Далее создадим переменную, которая будет хранить количество слов, удовлетворяющих нашему условию.

cnt = 0

3. Затем напишем конструкцию, с помощью которой будем перебирать все возможные слова.

for i in permutations(«УМСКЛ»):

4. Далее проверяем, что на первом месте не должна стоять буква У (не забываем, что индексы нумеруются с 0).

if i[0] != «У»:

5. Если слово подошло под условие, то к нашему счетчику прибавляем 1.

cnt += 1

6. Когда закончился перебор всех слов — выписали количество слов. Это и будет ответом.

print(cnt)

Полный код программы:
from itertools import permutations

cnt = 0
for i in permutations(«УМСКЛ»):
if i[0] != «У»:
cnt += 1
print(cnt)

Вывод программы: 96

Может показаться, что эту задачу легче решить вручную, расписывая слова по условию. Да, возможно! Но бывают и трудные задачи, требующие достаточно много времени для расчетов, поэтому лучше освоить программное решение, чтобы уметь проверить себя.

В этой статье мы познакомились с комбинаторикой, освоили новый модуль в Python. Приглашаем познакомиться с не менее интересной статьей «Функции и рекурсия», посвященной функциям и их применению в информатике.

Фактчек

Размещения — наборы последовательностей определенной длины, состоящие из определенных символов, которые могут встречаться в последовательности сколько угодно раз. Количество размещений N зависит от длины последовательности k и количества символов n как \(N=n^k\).
Перестановки — наборы последовательностей, отличающиеся только порядком следования символов друг за другом. Количество перестановок N зависит от количества символов в них n как N = n!.
В общем виде количество комбинаций высчитывается как произведение количества возможных символов на каждой позиции.
Для записи перестановок в Python используется permutations из модуля itertools, для записи размещений — product из того же модуля.

Проверь себя

Задание 1.
Сколько будет размещений длиной 5, состоящих из набора 123?

Задание 2.
Что такое перестановки?

Комбинации, состоящие из символов определенного набора, разной длины.
Комбинации, состоящие из символов определенного набора, одной длины.
Комбинации, состоящие из символов определенного набора и отличающиеся только порядком следования символов друг за другом.
Комбинации, состоящие из символов определенного набора и отличающиеся только длиной.

Задание 3.
Сколько может быть паролей длиной 4, состоящих из набора символов ПАРОЛЬ, в которых любой символ может использоваться сколько угодно раз, кроме Ь (используется только один раз и только на последнем месте)?

Задание 4.
Какая из записей на языке Python создаст размещения набора ПАРОЛЬ длиной 4?

itertools(“ПАРОЛЬ”, repeat = 4)
product(4, repeat = “ПАРОЛЬ”)
permutations(“ПАРОЛЬ”, repeat = 4)
product(“ПАРОЛЬ”, repeat = 4)

Ответы: 1. — 1; 2. — 3; 3. — 3; 4. — 4.

Информатика Комбинаторика

Понравилась статья? Оцени: