Так запросто, только нужно понимать, что не нужно считать факториалы по отдельности.
Например:
C(100,3)=100!/(97!*3!)=100*99*98/3*2*1= 98*50*33=161700
Вполне просто.
Руслан, что-то туго идёт разговор: и отвечаете вы в пустоту (надо - адресно, тогда собеседнику приходит уведомление), и отвечаете вы невпопад - я не спрашивал, как посчитать биноминальный коэффициент, я спрашивал - как вы с его помощью можете получить ответ к задаче.
Вы точно Senior Developer?
longclaps, С(n,k) - это в первую очередь функция из комбинаторики, которая как раз и даёт ответ на поставленную задачу. В данном случае ответ состоит из трёх вызовов:
С(n,1) - это можно не считать, оно всегда равно n
C(n,3)
C(n,5)
def c(n, k):
t = min(n - k, k)
n_fact = [n-i for i in range(t)]
for i in range(t):
for j in range(len(n_fact)):
if n_fact[j] % (i + 1) == 0:
n_fact[j] = n_fact[j] // (i + 1)
break
result = 1
for j in range(len(n_fact)):
result *= n_fact[j]
return result
print(c(500, 1))
print(c(500, 5))
print(c(500, 10))
Руслан, любопытная трактовка задачи. То есть вы решили, что раз задано 3 размера множеств, то и ответов должно быть 3? Вы не находите, что это немного странно: к одной задаче давать 3 условия и ожидать 3 варианта ответов? Вам не кажется, что трактовка "подсчитать количество способов разбить n элементов на множества размером 1, 5 или 10 элементов" более естественна?
Тут каждый вариант разбиения независим от других.
Если требуется сразу для 3 вариантов, то это будет сумма трех ранее найденных сочетания.
Т.е. вот так:
print(c(500, 1) + c(500, 5) + c(500, 10))
Если взять простой пример (чтобы руками посчитать), например для n=10, то д.б.
c(10, 1) = 10
c(10, 5) = 252
c(10, 10) = 1
Общая сумма 263.
Руслан, возьмём множество букв "abcdef" и размеры 1,2,3 (числа 5 и 10 великоваты для наглядного примера)
Тогда приемлимыми будут разбиения "a b c d e f", "ad be cf", "abf cde", но также "a bf cde", "a c bde f" - такая трактовка, похоже, кажется вам невероятной.
Тем не менее мною задача прочитана так. Руслан, что же до вашего решения, то оно неверно и в вашей же постановке задачи. Любопытно, сможете ли вы это понять самостоятельно.
longclaps, вы пропустили часть вариантов, вот например для размера 2:
ab, ac, ad, ae, af, bc, bd, be, bf, cd, ce, cf, de, df, ef
C(6,2) = 720/(2*24) = 15
longclaps, нет никакой разницы между разбить и выбрать.
Это стандартная комбинаторная задача: найти количество способов разбить множество на подмножества.
Но тут опять же нужен автор вопрос, чтобы расставить точки на и.
longclaps, Ок, давайте решим задачу в терминах этой вики.
Дано множество {a, b, c, d, e, f}, требуется найти количество разбиений этого множества непересекающимися подмножествами состоящими из 2 элементов.
Выбираем опорный элемент, например {a} и находим все возможные пары с этим элементом: {a, b},{a, c},{a, d},{a, e},{a, f} - всего 5 пар.
Теперь для каждой пары находим количество разбиений из оставшихся 4 элементов.
Например для пары {a, b} имеем такие варианты:
Вариант 1- {c, d}, {e, f}
Вариант 2- {c, e}, {d, f}
Вариант 3- {c, f}, {d, e}
Т.е. всего имеем 5 исходных пар умноженное на 3 разбиения для каждого, равно 15 возможных разбиений.
Что как раз и есть C(6,2) =15
Разбие́ние мно́жества — это представление его в виде объединения произвольного количества попарно непересекающихся подмножеств.
Где тут написано, что они должны быть одного размера?
Но это полбеды. Следи за руками, я повторю твои выкладки для размера 3:
Выбираем опорный элемент, например {a} и находим все возможные тройки с этим элементом: abc,abd,abe,abf,acd,ace,acf,ade,adf,aef - всего 10 троек.
Теперь для каждого подмножества находим количество разбиений из оставшихся 3 элементов.
Например для тройки abc имеем такие варианты:
Вариант 1- def - и всё!
Т.е. всего имеем 10 исходных троек умноженное на 1 разбиение для каждого, равно 10 возможных разбиений.
Что ни разу не есть C(6,3) = 20
longclaps, И снова вы не все варианты учитываете, вот смотрите:
Для опорного элемента {a} как уже выяснили 10 троек,
но теперь берем опорный элемент {b} и считаем тройки
{bcd} {bce} {bcf} {bde} {bdf} {bef} - т.е. еще 6 троек
теперь берем опорный элемент {c}:
{cde} {cdf} {cef} - еще 3 тройки
и наконец опорный элемент{d}
{def} - 1 тройка.
В итоге 10 + 6 + 3 + 1 = 20, что и есть C(6, 3) = 20
Руслан, это волшебно )))
итак, допустим (тут правда очень смешно, но приходится оговаривать), что порядок следования подмножеств неважен, как и порядок элементов в подмножествах, т.е.
если вам кажется, что порядок следования подмножеств и элементов в них важен - для обоих размеров будет по 6! == 720 разбиений, не буду их приводить.
если вам кажется, что порядок следования подмножеств важен, а элементов в них нет - для разбиения по 2 - 90, по 3 - 20.
если вам кажется, что порядок следования подмножеств не важен, а элементов в них важен - для разбиения по 2 - 120, по 3 - 360.
Я в упор не вижу расклада, при котором всплывала бы именно ваша пара чисел - по 2 - 15, по 3 - 20
Не вынуждайте меня присылать эти чертовы разбиения, попробуйте построить их самостоятельно програмкой, и расскажите о своих результатах, посмотрим на расхождения ))))
longclaps, Нет, порядок не важен, два подмножества содержащие одинаковые элементы равны и поэтому их не должно быть. Поэтому ваш вариант разбивки 6 элементов на 2 группы правильный, тут я тупанул.
Тут логика даже проще, без перебора: 6 элементов можно разбить по 3 на 20 разных троек, но чтобы покрыть множество из 6 элементов нужны 2 тройки и поэтому разбивок группами по 3 элемента больше чем 10 при двух группах (3 +3 и 20/2 = 10) быть не может.
И да формула в лоб не работает (C(n, k)), тут очень сильно влияет количество групп на которое нужно побить исходное множество, если их больше двух, то появляются дополнительные варианты по переносу элементов из группы в группу.
Теперь по условию задачи, разбить на группы из 1, 5, 10 элементов можно только множество из числа элементов кратного 10 (иначе не выйдет целого количества групп), т.е. процедура определения количества разбиений должна выдавать результат только для чисел вида 10^n, для остальных чисел разбиение не определено.
И теперь например для варианта, где n = 10, количество разбиений:
группами по 1 элементу = 1
группами по 10 элементов = 1
группами по 5 элементов = 126
(
имеем 2 группы по 5 элементов
Берем два опорных элемента 1 и 10, с ними получаем 2 варианта:
вариант 1:
группа 1 {1,_,_,_,_}
группа 2 {10,_,_,_,_}
Из оставшихся 8 элементов выбираем любые 4, это можно сделать C(8, 4) = 70 вариантов
вариант 2:
группа 1 {1,10,_,_,_}
группа 2 {_,_,_ ,_,_}
Из оставшихся 8 элементов выбираем любые 3, это можно сделать C(8, 3) = 56 вариантов
Итого 70+56 = 126 вариантов
)
общее количество = 128
Но если запустить вашу процедуру то получаем 9, как объяснить этот расчет?
Руслан, на самом деле я там лажу написал ))) Можно как-то так примерно:
from math import factorial as f
def partition(n, steps):
def merge(aa, bb):
cc = {}
for i, a in aa.items():
for j, b in bb.items():
k = i + j
if k <= n:
cc[k] = cc.get(k, 0) + a // b
return cc
res = {0: f(n)}
for step in steps:
res = merge(res, {i * step: f(step) ** i * f(i) for i in range(n // step + 1)})
return res.get(n, 0)
На простых примерах, где можно посчитать на пальцах, вроде работает:
print(partition(6, [2])) # 15, как и ожидалось
print(partition(6, [3])) # 10 -//-
print(partition(6, [2, 3])) # 25 - тут простая сумма, так как
# в разбиении либо только пары, либо только тройки
print(partition(5, [2, 3])) # 10 - тут как раз биноминальный коэфф,
# так как делим на 2 и 3 буквы
print(partition(7, [2, 3])) # 105 - тут возможно лишь разбиение 3+2+2
print(partition(10, [1, 5, 10])) # 380
