python - 使用 3 个常量查找所有可能的排列

Question

因为我确定你们都知道“真正的 donut 店问题”(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 = crate 数量，
• K = 一个 crate 可以容纳的最大可能瓶子数

每个箱子的K都不一样，不一定要满，也可以是空的。

因此，如您所见，我正在计算将 X 个给定的瓶子放入 X 个给定的 crate 中的可能性，其中一个 crate 最多可容纳 X 个瓶子。

更好理解的示例:比方说，我们有:

• 7 瓶 (n)
• 2 个 crate (k) -> [k1, k2]
• k1 适合 3 个瓶子(K1)，k2 适合 5 个瓶子(K2) [k1 -> 3, k2 -> 5]

所以它们有 2 种可能性可以将瓶子装入 crate 。

另一个:

• 7 瓶 (n)
• 3 个 crate (k) -> [k1, k2, k3]
• k1 适合 2 个瓶子，K2 适合 3 个瓶子，K3 适合 4 个瓶子

6 种可能性

上面的代码计算出完美无缺，但是当我用这样的方式尝试时:

问题:

• 30 瓶(n)
• 20 个 crate (k)
• k1 -> 1 瓶(K1)，k2 -> 2 瓶(K2)，k3 -> 3 瓶(K3) , k4 -> 4 Bottles (K4).. 依此类推直到 k20 -> 20 Bottles (K20)，我相信你明白了..

这需要永远，所以我问你；

问题:

我怎样才能改进上面的代码/功能？

Answer 1

您的问题是计算次数呈指数级增长。但是这些计算是在一遍又一遍地计算同一件事。

解决方案是存储中间值 AKA memoization。

这是 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 并立即获得。

如果你没有 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) 存储为表的键的问题。