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

说明：

• n=瓶数
• k=板条箱数量
• K=一个板条箱可容纳的最大可能瓶子数

每个板条箱的K值不同，不需要装满，甚至可以是空的。你知道吗

所以，正如你所看到的，我在计算它们有多少可能性，在给定的箱子里装X个给定的瓶子，其中一个箱子最多能装X个瓶子。你知道吗

更好理解的示例： 假设我们有：

• 7瓶（n）
• 2个板条箱（k）->；[k1，k2]
• k1适合3瓶（k1），k2适合5瓶（k2）[k1->；3，k2->；5]

因此，将瓶子装入板条箱的可能性2。你知道吗

另一个：

• 7瓶（n）
• 3个板条箱（k）->；[k1，k2，k3]
• k1适合2瓶，K2适合3瓶，K3适合4瓶

6可能性

上面的代码计算出完美无瑕，但当我尝试使用以下代码时：

问题：

• 30瓶（n）
• 20箱（k）
• k1->；1瓶（k1），k2->；2瓶（k2），k3->；3瓶（k3），k4->；4瓶（k4）。。一直到k20->；20瓶（k20），我相信你会明白的。。你知道吗

它需要永远，所以我问你

问题：

如何改进上述代码/功能？你知道吗

Answer 1

你的问题是计算次数的指数膨胀。但这些计算是在反复计算同一件事。你知道吗

解决方案是存储中间值。你知道吗

下面是python3.2的一个版本，使用functools.lru\u缓存为你写回忆录

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，并立即获得。你知道吗

如果没有python 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）存储为表键的问题。你知道吗