Задача no 317 число сочетаний

Условие задачи

Факториал числа n – произведение всех натуральных чисел от 1 до n:

Сочетанием из n по k называют набор из k элементов, выбранных из данного множества, содержащего n различных элементов. При этом наборы, отличающиеся только порядком следования элементов, считаются одинаковыми.

Число возможных сочетаний из n по k вычисляется по следующей формуле:

По заданным целым числам n и k требуется вычислить число сочетаний.

При решении данной задачи необходимо реализовать функцию F (n), вычисляющую факториал числа.

Определение числа сочетаний

Пусть имеется $n$ различных объектов. Чтобы найти число сочетаний из $n$ объектов по $k$, будем выбирать комбинации из $m$ объектов все возможными способами, при этом будем обращать внимание на разный состав комбинаций, но не порядок (он тут не важен, в отличие от размещений).

Например, есть три объекта <1,2,3>, составляем сочетания по 2 объекта в каждом. Тогда выборки <1,2>и <2,1>- это одно и то же сочетание (так как комбинации отличаются лишь порядком). А всего различных сочетаний из 3 объектов по 2 будет три: <1,2>, <1,3>, <2,3>.

На картинке наглядно проиллюстрировано получение всех возможных сочетаний из 4 различных объектов по 2 (их будет 6, см. калькулятор сочетаний ниже, который даст формулу расчета).

Общая формула, которая позволяет найти число сочетаний из $n$ объектов по $k$ имеет вид:

Найти сочетания из n по k

Чтобы вычислить число сочетаний $C_n^k$ онлайн, используйте калькулятор ниже.

Видеоролик о сочетаниях

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

Читайте также:  Драйвера для передней звуковой панели windows 10

Расчетный файл из видео можно бесплатно скачать

Полезные ссылки

Решебник по ТВ

Решебник с задачами по комбинаторике и теории вероятностей:

Число сочетаний можно найти используя рекурсию и, соответственно, рекуррентное соотношение. Код получается вот такой:

Но я знаю, что рекурсия штука не быстрая и не всегда надежная. Есть ли другие алгоритмы и на сколько они быстрые?

2 ответа 2

Через факториал медленно и не эффективно.
В формуле n! / (k! (n — k)!) , если сократить, то получится (n-k+1)(n-k+2)...n/k!

Получается такой код:

Также можно посмотреть библиотеку itertools :

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

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

Оцените статью
Adblock
detector