0

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

def C(n, k):
    if k == n or k == 0:
        return 1
    if k != 1:
        return C(n-1, k) + C(n-1, k-1)
    else:
        return n


print(C(int(input()), int(input())))

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

7
  • 3
    Число сочетаний можно как бы найти и без рекурсии, используя прямую формулу... особенно если есть готовый оператор вычисления факториала или таблица факториалов. В крайнем случае - один цикл.
    – Akina
    16 авг 2019 в 11:38
  • 2
    В школе же формулу проходят?
    – andreymal
    16 авг 2019 в 11:39
  • 2
    n! / (k! (n - k)!). Факториал реализован в функции math.factorial. Ваш алгоритм не оптимален, но не потому, то рекурсия медленная, а потому, что результаты не кешируются. @functools.lru_cache(None) значительно ускорит программу.
    – extrn
    16 авг 2019 в 11:41
  • @andreymal, это конечно да, но там факториалы, считать которые совсем не хочется, это тоже не быстро 16 авг 2019 в 11:54
  • @AntivistHome подозреваю, что всяко быстрее рекурсии :)
    – andreymal
    16 авг 2019 в 11:59

4 ответа 4

4

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

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

def С(n, k):
    if 0 <= k <= n:
        nn = 1
        kk = 1
        for t in xrange(1, min(k, n - k) + 1):
            nn *= n
            kk *= t
            n -= 1
        return nn // kk
    else:
        return 0

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

combinations('ABCD', 2)  # AB AC AD BC BD CD
4

используйте math.comb

import math

n = int(input())
k = int(input())

print(math.comb(n, k)) 
1

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

import itertools

def C(n, k):
    return len(list(itertools.combinations(range(1, n), k)))

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

4
  • @0andriy Почему не вынесли в ответ?
    – V-Mor
    17 авг 2019 в 7:14
  • 5
    @V-Mor Генерировать сочетания, чтобы узнать их количество - неразумно, т.к. существуют простые формулы
    – MBo
    17 авг 2019 в 18:05
  • 1
    место len(list(...)) лучше писать sum(1 for _ in ...)
    – Danis
    17 фев 2021 в 19:55
0

Для ТС уже неактуально, наверное, но может кому пригодится.

Треугольник Паскаля (сочетания - это биномиальные коэффициенты).

Чтобы его "нарисовать", умножать вообще не нужно.

Быстрее уже никак.

7

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.