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

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 в повседневной жизни. Я не могу решить для вас подобные задачи, но надеюсь, что данная статья поможет вам разобраться.

Специально для сайта ITWORLD.UZ. Новость взята с сайта NOP::Nuances of programming