Python 递归组合

Question

我该如何写一个函数来计算：

C(n,k)= 1                          if k=0
        0                          if n<k
        C(n-1,k-1)+C(n-1,k)     otherwise

到目前为止，我有：

def choose(n,k):
if k==0:
   return 1
elif n<k:
   return 0
else:

Answer 1

就像这样

def choose(n,k):
    if k==0:
        return 1
    elif n<k:
        return 0
    else:
        return choose(n-1,k-1)+choose(n-1,k)

编辑

这是一个简单的方法，如果想要更高效的做法，可以去看看维基百科和spencerlyon2的回答

Answer 2

你想要计算从n个元素中选择k个元素的选项数量：

def choose(n,k):
    if k == 0: 
       return 1 # there's only one option to choose zero items out of n
    elif n < k:
       return 0 # there's no way to choose k of n when k > n
    else:
        # The recursion: you can do either
        # 1. choose the n-th element and then the rest k-1 out of n-1
        # 2. or choose all the k elements out of n-1 (not choose the n-th element)
        return choose(n-1, k-1) + choose(n-1, k)

Answer 3

从指数时间改进到线性时间

到目前为止，所有的答案都运行在指数时间 O(2n)。不过，只需改一行代码，就可以让它运行在 O(k) 的时间复杂度。

---

解释：

之所以会有指数时间的原因是，每次递归都会把问题分成重叠的子问题，这一行代码就是罪魁祸首（可以在这里查看）：

def choose(n, k):
    ...
    return choose(n-1, k-1) + choose(n-1, k)

为了理解为什么这样不好，我们来看一个例子：choose(500, 2)。计算 500 choose 2 的数值是 500*499/2；然而，使用上面的递归方法却需要进行 250499 次递归调用才能计算出来。显然，这样做太过了，因为实际上只需要3次操作就够了。

要把这个改进到线性时间，你只需要选择一个不同的递归方法，这种方法不会分成两个子问题（在维基百科上有很多这样的例子）。

例如，下面的递归方法是等效的，但只需要 3 次递归调用就能计算 choose(500,2)（可以在这里查看）：

def choose(n,k):
    ...
    return ((n + 1 - k)/k)*choose(n, k-1)

改进的原因在于，每次递归只有一个子问题，并且每次调用都会把 k 减少 1。这意味着我们可以保证这个递归只需要 k + 1 次递归，也就是 O(k)。这对于只改一行代码来说，真是个巨大的进步！

如果你想进一步提升，可以利用“n choose k”的对称性，确保 k <= n/2（可以在这里查看）：

def choose(n,k):
    ...
    k = k if k <= n/2 else n - k            # if k > n/2 it's equivalent to k - n
    return ((n + 1 - k)/k)*choose(n, k-1)

Answer 4

这是来自维基百科的解决方案，关于二项式系数的内容。你可以在这里查看详细信息：http://en.wikipedia.org/wiki/Binomial_coefficient

def choose(n, k):
    if k < 0 or k > n:
        return 0
    if k > n - k: # take advantage of symmetry
        k = n - k
    if k == 0 or n <= 1:
        return 1
    return choose(n-1, k) + choose(n-1, k-1)

Answer 5

假设你提问中缺少的操作符是减法运算符（感谢lejlot），那么这个就是答案：

def choose(n,k):
  if k==0:
     return 1
  elif n<k:
     return 0
  else:
     return choose(n-1, k-1) + choose(n-1, k)

需要注意的是，在大多数Python系统中，最大递归深度或递归限制只有1000。超过这个限制就会抛出一个异常。你可能需要通过将这个递归函数改成迭代的方式来解决这个问题。

下面是一个示例迭代函数，它使用栈来模拟递归，同时避免了Python的最大递归限制：

def choose_iterative(n, k):
  stack = []
  stack.append((n, k))
  combinations = 0

  while len(stack):
    n, k = stack.pop()
    if k == 0:
      combinations += 1
    elif n<k:
      combinations += 0 #or just replace this line with `pass`
    else:
      stack.append((n-1, k))
      stack.append((n-1, k-1))

  return combinations