python - 用3个常数找到所有可能的排列

因为我确信你们都知道“真正的甜甜圈店问题”（https://math.stackexchange.com/questions/223345/counting-donuts）所以我就开始…
我有三个整数，三个都是用户输入的。有了它们，我需要计算它们有多少可能的排列。我已经有了一些代码，它可以很好地处理小整数，如果它们变大了，我的工具可以运行几天/几个小时？
计算可能排列的递归函数：

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))

说明：
n=瓶数
K=板条箱数量，
K=最大数量的可能的瓶子一个板条可以适合
每个板条箱的K不同，不需要装满，甚至可以是空的。
所以，正如你所看到的，我计算他们有多少可能性，以适应X给定瓶子内的X给定板条箱，其中一个板条箱可以适应最大的X瓶。
更好理解的例子：
比如说，我们有：
7瓶（N）
2箱（k）—>[k1，k2]
K1适合3瓶（K1），K2适合5瓶（K2）[K1->3，K2->5]
所以他们有两种可能把瓶子装进板条箱。
另一个：
7瓶（N）
3箱（k）—>[k1、k2、k3]
k1适合2瓶，k2适合3瓶，k3适合4瓶
6种可能性
上面的代码计算出的是完美的，但是当我尝试使用like时：
问题：
30瓶（n）
20箱（K）
一瓶（k1），二瓶（k2），三瓶（k3），四瓶（k4）。等等，直到k20->20瓶（k20），我肯定你知道了。。
它需要永远，所以我问你；
问题：
如何改进以上代码/功能？

最佳答案

你的问题是计算次数的指数膨胀。但这些计算是一次又一次地计算同一件事。
解决方案是存储中间值（也称为记忆）。
下面是Python3.2中的一个版本，它使用functools.lru缓存为您执行备忘录

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，并立即得到。
如果没有Python3.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）存储为表键的问题。

关于python - 用3个常数找到所有可能的排列，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/33318054/