Модуль random. Часть 4 | Программирование на Питоне

Модуль random. Часть 4

Все курсы > Программирование на Питоне > Занятие 10 (часть 4)

Рассмотрим способы расчета комбинаций с помощью Питона. Помимо модуля random изучим модуль itertools.

Продолжим работать в том же ноутбуке

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

np.random.shuffle() и np.random.permutation()

Обе эти функции перемешивают (shuffle) или переставляют (permute) элементы списка или массива. Основное отличие заключается в том, что np.random.shuffle() изменяет исходный массив, а np.random.permutation() создает «перемешанную» копию исходного массива:

Перемешивание массива можно использовать, если, например, нужно внести элемент случайности в работу с данными. Давайте создадим аналог функции train_test_split() библиотеки sklearn, которой мы пользовались для разделения выборки на обучающую и тестовую части.

Подгрузим данные о пациентах с диабетом из модуля datasets библиотеки sklearn. Как это делается, мы подробно разобрали на занятии по линейной регрессии на вводном курсе.

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

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

функция для разделения выборки на обучающую и тестовую части
функция для разделения выборки на обучающую и тестовую части 2

Похоже, что все работает как надо.

Модуль itertools

Рассмотренные выше функции не позволяют вывести все возможные комбинации элементов. Для этого есть модуль itertools.

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

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

Перестановки без замены

Вначале возьмем те случаи, когда один элемент может повторяться только один раз. В этом случае мы говорим о перестановках без замены (permutations without replacement). Они бывают двух видов: без повторений и с повторениями.

Перестановки без повторений

Рассмотрим простой пример. У нас есть три элемента A, B и C. Сколькими способами можно переставить эти объекты так, чтобы порядок элементов не повторялся?

Так как элементы в исходном множестве не повторяются, то такая перестановка называется перестановкой без повторения (permutation without repetition).

Очевидно, на первое место мы можем поставить любой из трех элементов, на второе — только один из оставшихся двух, на третьем месте окажется единственный не выбывший элемент. Получается $ 3 \times 2 \times 1 = 6 $. Такой расчет не что иное, как факториал числа три, $3!$.

$$ P(n) = n! \rightarrow P(3) = 3! = 6 $$

На Питоне мы можем вычислить факториал нужного нам числа через функцию factorial() модуля math.

Кроме того, мы можем воспользоваться функцией permutations() модуля itertools. В этом случае мы можем вывести все возможные перестановки элементов множества.

Если все же нас интересуют не сами перестановки, а их количество, можно воспользоваться функцией len().

Размещения

Приведем чуть более сложный пример. Предположим, в соревнованиях участвуют шесть команд ($n = 6$), и нам нужно узнать, сколькими способами эти команды могут занять первое, второе и третье призовые места. Просто вычислить факториал мы уже не можем, нам нужно уменьшить общее число вариантов на то количество перестановок, которое не будет реализовано, потому что мест всего три ($r = 3$).

Такой тип перестановок называют размещением (partial permulation). Приведем формулу.

$$ P(n, r) = \frac{n!}{(n-r)!} \rightarrow P(6, 3) = \frac{6!}{(6-3)!} = 120 $$

На Питоне мы можем применить ту же функцию permutations(), передав ей через параметр $r$ размер выборки (количество мест).

Посмотрим на общее количество перестановок.

Дополнительно замечу, что в случае если выборка $r$ также велика, как и множество $n$ (первый пример), то формулу размещения можно записать как

$$ P(n, n) = \frac{n!}{(n-n)!} $$

В знаменателе получается $0!$, и для того чтобы избежать деления на ноль, принято считать, что факториал нуля равен единице, $0! = 1.$

Перестановки с повторениями

Давайте дополнительно усложним задачу и рассчитаем количество перестановок букв в слове «молоко». В данном случае мы не можем воспользоваться факториалом, потому что буква «о» повторяется трижды, и соответственно мы можем разместить ее $3!$ способами. Как следствие, для получения правильного ответа нам нужно разделить количество перестановок на шесть, $3! = 6.$

В таком случае мы говорим про перестановки с повторениями (permutations with repetitions).

$$ \frac{6!}{3!} = 120 $$

В целом, если какой-то из элементов повторяется, то общее число перестановок нужно разделить на произведение факториалов повторяющихся элементов (правильнее сказать на произведение факториалов повторяемости каждого элемента, однако факториал неповторяющихся элементов равен $1! = 1$, поэтому ими можно пренебречь).

$$ \frac{P(n, r)}{n_1! \cdot n_2! \cdot … \cdot n_r!}, \text{где } n_1! + n_2! + … + n_r! = n $$

Для расчета перестановок с повторениями напишем собственную функцию.

Рассчитаем количество перестановок с повторениями букв в слове «молоко».

Перестановки с заменой

Перестановки с заменой (permutations with replacement), когда элементы могут использоваться более одного раза, есть не что иное, как прямое или декартово произведение множества само на себя.

Вначале рассмотрим суть декартова произведения.

Декартово произведение (Cartesian product) двух множеств предполагает, что мы создаем все возможные упорядоченные пары исходных множеств.

В частности, если у нас есть одно множество $A$ с элементами $\{ 1, 2, 3 \}$ и множество $B$ с элементами $ \{ x, y \} $, то их произведением $ A \times B $ будут все возможные упорядоченные комбинации этих элементов.

декартово произведение

При умножении множества само на себя один раз мы говорим про квадрат Декарта (Cartesian square). В частности, если умножить множество действительных чисел $ \mathbb {R} $ само на себя ($ \mathbb{R} \times \mathbb{R} $), то получится координатная плоскость или декартова система координат (Cartesian plane).

координатная плоскость или декартова система координат

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

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

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

возможные варианты заказа

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

В модуле itertools для такой операции есть функция product().

В целом формула прямого произведения выглядит как $n^r$. Например, если во множестве четыре элемента, то поставить два элемента из этих четырех можно шестнадцатью способами ($4^2=16$).

Убедимся, что таких способов 16.

В данном случае мы умножаем множество само на себя два раза.

умножение множества само на себя два раза

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

способы перестановок

Сочетания

Сочетания без повторений

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

сочетания

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

$$ P(5, 2) = \frac{5!}{(5-2)!} = 20 $$

Для наглядности посмотрим на эти комбинации с помощью Питона.

Однако обратите внимание, некоторые комбинации, если не учитывать порядок, повторяются (например, $AB$ и $BA$). Поэтому сочетаний (то есть перестановок без учета порядка) меньше. Причем меньше на количество перестановок каждого типа, то есть $r!$. В данном случае перестановок каждого типа два, то есть $2! = 2$.

Выведем формулу.

$$ C(n, r) = \frac{n!}{(n-r)! r!} \rightarrow C(5, 2) = \frac{5!}{(5-2)! 2!} = 10 $$

В Питоне для сочетаний есть удобная функция combinations().

Сочетания с повторениями

Если допустить повторение элементов, сочетаний станет больше.

В целом количество сочетаний с повторениями (combinations with repetitions или иногда with replacement) вычисляется по следующей формуле.

$$ C(n, r)_{rep} = \frac{(n+r-1)!}{(n-r)! r!} $$

В нашем случае,

$$ C(2, 2)_{rep} = \frac{(2+2-1)!}{(2-2)! 2!} = \frac{3!}{2!} = 3 $$

Биномиальные коэффициенты

Давайте вернемся к биномиальному распределению и его функции вероятности. Напомню, что во втором примере мы три раза подбрасывали монету, $n = 3$, вероятность выпадения орла составляла, $p = 0{,}7$, а найти мы должны были выпадение двух орлов, $k = 2$.

$$ P(X = k) = C(n, k) p^k (1-p)^{n-k} $$

$$ P(X = 2) = C(3, 2) \times 0{,}7^2 \times (1-0{,}7)^{3-2} = 3 \times 0{,}7^2 \times 0{,}3^1 = 0{,}441 $$

Первая часть этой формулы и есть количество сочетаний при выпадении двух орлов в трех бросках. Для того чтобы вывести дерево вероятностей, мы можем воспользоваться декартовой степенью множества {решка, орел} или {H, T}.

Количество же сочетаний рассчитаем через функцию combinations().

Полный расчет на Питоне будет выглядеть так.

Конечно же этот результат гораздо проще получить через библиотеку scipy.

Подведем итог

По большому счету мы затронули три важные темы:

  1. Моделирование и исследование случайных процессов с помощью модуля random;
  2. Дискретные и непрерывные распределения случайных величин; и
  3. Комбинаторику на Питоне.

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

Вопросы для закрепления

Вопрос. Чем теоретическая вероятность отличается от эмпирической?

Посмотреть правильный ответ

Вопрос. Чем отличается функция вероятности (probability mass function, pmf) от плотности вероятности (probability density function, pdf)?

Посмотреть правильный ответ

Вопрос. Чем сочетания отличаются от перестановок?

Посмотреть правильный ответ

В конце ноутбука приведены дополнительные упражнения⧉.

На следующем занятии мы немного отдохнем от математики и рассмотрим объектно-ориентированный подход к программированию.


Ответы на вопросы

Вопрос. Подскажите, а зачем повторно импортировать Numpy, itertools и math перед объявлением собственной функции permutations_w_repetition()? Ведь вы уже импортировали их перед этим.

Ответ. Я повторно импортировал необходимые библиотеки на случай использования функции в других проектах. Предположим, вы захотите использовать эту функцию в своей работе и поместите ее в отдельный файл. Для того чтобы код сработал, вам сначала понадобится импортировать эти три библиотеки.

По-английски они называюся dependency или dependencies, потому что от них зависит выполнение основной программы.

Дополнительно замечу, что Руководство по написанию кода на Питоне (Python Enhancement Proposal или PEP 8) рекомендует⧉ делать импорт необходимых библиотек и модулей «после комментариев к модулю и строк документации, и перед объявлением констант», а не внутри функций или классов. Подробнее об этом мы поговорим через одно занятие.


Вопрос. Скажите, а чем матожидание отличается от среднего значения?

Ответ. Матожидание (expected value) — это то среднее значение, которое мы предполагаем/ожидаем получить с учетом известного нам типа распределения. Например, зная, что случайная величина следует биномиальному распределению с параметрами $n = 3$ и $p = 0{,}7$, мы ожидаем наблюдать среднее значение $np = 3 \times 0{,}7 = 2{,}1$. В частности, с помощью функции scipy.stats.binom.stats() мы рассчитываем именно матожидание распределения.

Собрав же фактические данные (мы для этого использовали модуль random и функцию np.random.binomial()), мы можем посмотреть насколько среднее (mean value) этих данных согласуется с математическим ожиданием. При достаточно большом количестве экспериментов среднее должно стремиться к математическому ожиданию.

Привел пример в конце ноутбука⧉.