В этом видео мы обсудим, как генерируются сочетания, с повторениями и без, на Python, а также обсудим подсчет биномиальных коэффициентов. Давайте начнем с сочетаний. В случае сочетаний без повторений мы просто загружаем соответствующую функцию из библиотеки "itertools" (это функция "combinations"), и генерируем все сочетания с помощью этой функции. Она получает два аргумента: первый — это алфавит, здесь у нас пять символов (a, b, c, d и e), а второй — это размер сочетания, то есть здесь мы хотим получить сочетание размера три, и дальше мы всех их печатаем. Давайте запустим, посмотрим. Действительно, вот они все напечатались — замечательно. Давайте перейдем к сочетаниям с повторениями. Если у нас сочетание с повторениями, то мы загружаем другую функцию из той же библиотеки, "combinations_with_replacement", и используем ее; аргументы те же, тот же алфавит, количество элементов, которые мы хотим получить в сочетании (здесь мы их хотим получить два), и, собственно, запускаем. Получаются у нас всевозможные сочетания из двух символов с повторением — видно, что символы могут повторяться: у нас "а" два раза встречается, "b" два раза встречается. Мы можем, например, запустить это и для "тройки" тоже; тогда у нас будут все сочетания размера три, видно, что их сильно больше, чем случаев без повторений; все они здесь встречаются, можно на это посмотреть. Дальше, с помощью этого, мы можем решить задачу, которую мы уже разбирали, — про салаты из помидоров, огурцов, перцев и баклажанов. Значит, здесь мы просто можем сгенерировать все эти салаты, а потом посчитать их количество. Как мы генерируем эти салаты? Здесь у нас четыре символа: "T" — это помидоры (tomatoes), "C" — это огурцы (cucumbers), "B" — это перцы (bell peppers) и "E" — это баклажаны (egg plants), так что вот все эти салаты, то есть вот весь этот алфавит; мы cгенерируем сочетания с повторениями размера семь, и дальше просто подсчитываем длину этого списка — получается, что у нас просто подсчитывается количество этих сочетаний. Давайте запустим и действительно убедимся, что их 120, как мы и видели в лекции. На самом деле, с помощью генераций этих списков, с помощью генераций сочетаний мы можем так же подсчитывать и какие-то более специальные типы салатов, например, мы можем решить такую задачу: мы хотим посчитать, сколько есть салатов, в которых помидоров больше, чем огурцов. Представим, что мы помидоры любим больше, чем огурцы, и хотим посчитать все такие салаты. Давайте попробуем. Их, оказывается, будет 50. Как мы это делаем? Мы перебираем все такие салаты и для каждого салата проверяем, верно ли, что в нем "T" встречается больше раз, чем "C", то есть то, что помидоров больше, чем огурцов. И если это происходит, то мы увеличиваем счетчик на единицу. Получается, значит, у нас 50 таких салатов (так, извините), и мы можем даже их все напечатать, давайте это сделаем — запустим на печать; вот они все тут, собственно, и напечатались; видно, что в них во всех помидоров действительно больше, чем огурцов, то есть если, например, помидоров у нас два — здесь две буквы "T", то огурец будет тут один. А потом остаются случаи вообще без огурцов. Здесь 50 получилось в той же строке — давайте тогда добавим просто строку пустую, которая будет печататься после нашего списка, и тогда у нас число салатов будет в отдельной строке. В принципе, мы можем напечатать, на самом деле, все салаты. Давайте быстро это сделаем. Действительно, если мы перенесем печать до "if", то просто напечатаются все салаты. Давайте попробуем — и мы увидим, что печатаются они, в общем-то, в том же порядке, в котором мы их и перебирали в нашей лекции: сначала будет салат из всех помидоров, потом салат из всех помидоров, кроме одного огурца, одного перца, одного баклажана; потом случай, когда помидоров на один меньше и так далее — они, на самом деле, в том же порядке перебираются и тут. Давайте обсудим теперь подсчет биномиальных коэффициентов и просто разберем два алгоритма, которые мы видели в лекции. Первый, это когда мы просто пользуемся рекуррентным соотношением. Давайте заведем двумерный массив для чисел сочетаний, заведем его размера семь на семь, и у нас "C" от "n'' и "k" — это будет число сочетаний из "n" по "k". Тогда мы просто для всех "n", по порядку, делаем следующее: мы сначала заводим "C" (крайний биномиальный коэффициент у нас просто единица), а по всем остальным "k" от единицы до "n" мы подсчитываем их рекуррентно — вот наше рекуррентное соотношение. И потом можем просто напечатать вот этот биномиальный коэффициент, я вот уже запустил, и получилось 35. И второй способ: мы точно так же заводим массив, точно так же фиксируем, что у нас крайние биномиальные коэффициенты по единице, а очередной подсчитываем через соседний, то есть, соседний - один, то есть мы берем биномиальный коэффициент "C" из "n минус один" по "k минус один", умножаем его на "n" и делим на "k". Это то, что мы делали, убеждались; можете посмотреть на формулу и убедиться, что получается действительно "C" из "n" по "k", и вот это другой рекуррентный способ подсчета биномиальных коэффициентов. Также понятно, что подсчет биномиальных коэффициентов — есть встроенная функция, и мы можем загрузить библиотеку "scipy", там будет функция "comb", которая подсчитывает биномиальные коэффициенты, нужен специальный флажок, чтобы она подсчитывала точные значения (для больших биномиальных коэффициентов это важно), и здесь тоже будет 35. Вот есть такие способы подсчета биномиальных коэффициентов..