Найти все возможные перестановки с 3 константами

Question

так как вы уверены, что все знают о «Реальной проблеме магазина пончиков» (https://math.stackexchange.com/questions/223345/counting-donuts). Так что я просто начал ..

У меня есть 3 целых числа, все три введены пользователем. с ними мне нужно рассчитать, сколько возможных перестановок они есть. У меня уже есть код, он отлично работает для небольших целых чисел, если они увеличиваются, мой инструмент работает буквально в дни/часы?

рекурсивная функция для вычисления возможных перестановок:

def T(n, k, K): 
if k==0: return n==0 
return sum(T(n-i, k-1, K) for i in xrange(0, K[k-1]+1)) 

Пояснение:

• п = количество бутылок
• к = Количество ящиков,
• К = Максимальная Количество возможных бутылок в одном ящике может соответствовать

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

Итак, как вы видите, им нужно рассчитать, сколько их возможностей, чтобы соответствовать X указанным бутылкам внутри X заданных ящиков, где один ящик может вместить максимум X бутылок.

Пример для лучшего понимания: Допустим, мы имеем:

• 7 бутылок (п)
• 2 Кратет (к) -> [k1, k2]
• k1 подходит для 3 бутылок (K1), k2 подходит для 5 бутылок (K2)[k1 -> 3, k2 -> 5]

Так они возможности помещаются бутылки внутри ящиков.

еще один:

• 7 бутылок (п)
• 3 Кратет (к) -> [k1, k2, k3]
• k1 пригонки 2 бутылки, К2 соответствует 3 Бутылки, К3 подходит 4 бутылки

возможности

Над кодом рассчитывает, что безупречна, но когда я пытаюсь его как:

Проблема:

• 30 бутылок (п)
• 20 Crates (к)
• k1 -> 1 Бутылка (K1), k2 -> 2 Бутылки (K2), k3 -> 3 Бутылки (K3), k4 -> 4 Бутылки (К4) .. и так далее до К20 -> 20 бутылок (K20), я уверен, вы получите идею ..

Он принимает НАВСЕГДА, поэтому им просят вас;

Вопрос:

, как я мог бы улучшить выше кода/функции?

Answer 1

Ваша проблема - экспоненциальное раздутие количества выполненных вычислений. Но эти вычисления вычисляют одно и то же снова и снова.

Решение заключается в сохранении промежуточных значений.

Вот версия в Python 3.2, используя functools.lru_cache сделать запоминанием для вас

import functools 

    def T(n, k, K): 
     @functools.lru_cache(maxsize=None) 
     def Tsub(n,k): 
     if k==0: return n==0 
     return sum(Tsub(n-i,k-1) for i in range(0, K[k-1]+1)) 
     return Tsub(n,k) 

    print(T(7,2,[3,5])) 
    print(T(7,3,[2,3,4])) 
    print(T(30,20,list(range(20)))) 

На моей машине конечный результат 2172723680407 и сразу получается.

Если вы не имеете питона 3.2 вы можете сделать это следующим образом:

def T(n, k, K): 
    cache = {} 
    def Tsub(n,k): 
    key = (n,k) 
    if key in cache: 
     return cache[key] 
    if k==0: 
     cache[key] = (n==0) 
     return n==0 
    v = sum(Tsub(n-i,k-1) for i in xrange(0, K[k-1]+1)) 
    cache[key] = v 
    return v 
    return Tsub(n,k) 

print(T(7,2,[3,5])) 
print(T(7,3,[2,3,4])) 
print(T(30,20,list(range(20)))) 

Странная вложенности функций используется, чтобы обойти вопрос, который вы не можете сохранить список (K) как ключ к таблице.