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
{{abc}, {def}} == {{def}, {abc}}
{abc} == {acb} == ... == {cba}
ab cd ef
ab ce df
ab cf de
ac bd ef
ac be df
ac bf de
ad bc ef
ad be cf
ad bf ce
ae bc df
ae bd cf
ae bf cd
af bc de
af bd ce
af be cd
abc def
abd cef
abe cdf
abf cde
acd bef
ace bdf
acf bde
ade bcf
adf bce
aef bcd
Рад был оповестить вас об этом.