Вероятность в Python: перестановки и сочетания

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

Быстрый поиск в Google выявляет 4 основные математические темы, на которых основана вся область:

• Линейная алгебра
• Анализ
• Статистика
• Вероятность

Сегодня я расскажу о двух важнейших концепциях из теории вероятности: сочетаниях и перестановках. 

Начнем с базового определения самой вероятности: 

Вероятность — степень (относительная мера, количественная оценка) возможности наступления некоторого события. В теории вероятностей вероятность принимает значения от 0 до 1. Значение 1 соответствует достоверному событию, невозможное событие имеет вероятность 0. Чем выше значение, тем больше вероятность события.

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

Перед погружением в перестановки и сочетания, нужно понять еще один термин — факториал. 

Что такое факториал? 

Хороший вопрос. Согласно Википедии: 

Факториал — функция, определённая на множестве неотрицательных целых чисел. Факториал натурального числа n определяется как произведение всех натуральных чисел от 1 до n включительно.

Факториал вычисляется по следующей формуле: 

Вот пример:

Теперь вы, возможно, задумались, как вычислять факториалы в Python. Во многих библиотеках есть готовые функции, но создать собственную функцию тоже очень легко, и именно это мы и сделаем. 

Вот простая рекурсивная функция, которая справится с задачей: 

Теперь можно использовать эту функцию для проверки примера выше: 

Хорошо, но где факториалы используются в реальном мире? 

Скажем, в гонке участвуют пять человек, и вы хотите узнать количество способов, по которым эти пятеро могут финишировать первыми, вторыми или третьими. Можно взять листок бумаги и просто записать все возможные варианты, но зачем? Что если участников 100? 

Вот как эта задача решается с помощью факториалов: 

Это называется перестановка. 

Перестановки

И снова начнем с определения: 

В математике перестановка — это упорядочение членов набора в последовательность или, если последовательность уже определена, перестановка (изменение порядка) ее элементов. 

Существует два способа вычисления перестановок. Выбор способа зависит от того, разрешается повторение или нет. Давайте рассмотрим на примере.

У вас есть веб-сайт, на котором могут регистрироваться пользователи. Им нужно вводить пароль длиной строго в 8 символов, которые не должны повторяться. Сперва нужно определить, сколько букв и цифр в английском алфавите:

• количество букв: 26
• количество цифр: 10

То есть всего 36. Тогда n = 36, а r = 8, потому что пароль должен быть длиной в 8 символов. Зная это, мы легко можем рассчитать количество уникальных паролей, используя формулу: 

Если вы поспешили и посчитали вручную: 

В Python это тривиальная задача:

Здорово, но я хочу разрешить пользователям повторно использовать символы. Нет проблем, в данном случае это перестановки с повторениями, формула еще проще: 

Мы уже знаем, что n (36) и r (8), так что вот решение:

И снова реализация на Python тривиальна:

Это действительно большое число. Попробуйте произнести его вслух! 

Сочетания

Далее на повестке дня — сочетания. Вам наверняка любопытно, что это такое и в чем их отличие от перестановок. Начнем с определения: 

Сочетание— это выбор значений из набора, в котором (в отличие от перестановок) порядок выбора не имеет значения. 

Чтобы понять это определение, разберем следующий пример: группа людей, выбранных в команду — это та же самая группа, независимо от порядка участников. Вот и вся идея сочетаний. Если выбрать 5 членов команды, можно упорядочить их по имени, росту или другому параметру, но команда останется прежней — порядок не имеет значения. 

Давайте запишем это формулой. Количество сочетаний C набора из n объектов, взятых по r, рассчитывается так:

С этим уравнением мы можем решить следующую задачу: сколькими способами можно выбрать в футбольную команду 5 человек из 10? 

Группа будет той же, порядок значения не имеет. Значит, n = 10, а r = 5:

И это можно легко сделано в Python:

Великолепно! Но интересно, существует ли версия сочетаний с повторениями? Да! 

Представьте, что готовите сэндвич и по какой-то причине вам нужно использовать только 4 ингредиента из 10. Однако ингредиенты не должны быть уникальны, например, можно положить 3 куска сыра и 1 кусок салями. Как это здорово, я тоже обожаю сыр, вот спасибо!

Но как сформулировать эту идею математически? Ответ снова прост:

Давайте применим формулу к примеру выше. n снова равно 10 (потому что 10 возможных ингредиентов), а r = 4 (потому что выбрать можно только 4):

Используем Python для проверки:

 Превосходно. 

И напоследок 

Сочетания и перестановки математически просты, однако сложность заключается в том, как представить в такой форме реальные проблемы. Иногда бывает трудно выделить значения n и r в повседневной жизни. Я не могу решить для вас подобные задачи, но надеюсь, что данная статья поможет вам разобраться. 

---

Перевод статьи Dario Radečić: Essential Probability in Python: Permutations and Combinations