Источник: Nuances of Programming
Теория вероятности не сложная, по крайней мере, на уровне, необходимом для начала работы в науке о данных. Возможно, прошло какое-то время с тех пор, как вы познакомились с этой темой, и, если ваши знания немного ослабли, эта статья поможет вам вернуться в русло.
Быстрый поиск в 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 в повседневной жизни. Я не могу решить для вас подобные задачи, но надеюсь, что данная статья поможет вам разобраться.
Читайте также:
Читайте нас в телеграмме и vk
Перевод статьи Dario Radečić: Essential Probability in Python: Permutations and Combinations
