你能解释一下这个递归的"n选择k"代码吗？

Question

以下是参数n和k的子集问题的代码.n代表学生总数,k代表我想要离开的学生数量.该代码试图给出从n个学生中拉出k个学生的可能组合的数量.

def subset(n, k): 
    if k == 0:
        return 1
    if n == k:
        return 1
    else:
        return subset(n-1, k-1) + subset(n-1, k)

我理解递归调用的第一部分,但是我无法理解+子集(n-1,k)部分.任何人都可以向我解释这个吗？

Answer 1

递归是基于一个简单的观察,我将给出一个组合论证,为什么它是真的,而不是通过公式的数学证明.

无论何时选择k元素n,都有两种情况:

由于这些事件是互斥的,因此组合的总量由选择时的组合数量#n和不选择时的组合数量给出#n.

选择元素 `#n`

由于我们已经选择了一个元素,我们只需要选择另一个k-1元素.此外,由于我们已经决定了一个要素 - 关于它是否包括在内 - 我们只需要考虑其余n-1要素.

因此,选择元素的组合量#n由下式给出

    subset(n - 1, k - 1)

仍有一些k元素可供选择,但由于我们已经对元素做出了决定#n,因此只有n - 1元素可供选择.从而:

    subset(n - 1, k)

递归使用的事实是,我们通常可以区分两种情况,即元素n是解决方案一部分的解决方案,以及不是解决方案的解决方案.

但是,不能总是做出这样的区分:

在这些情况下,只有一个解决方案,因此

if k == 0:
    return 1
if n == k:
    return 1

要做到这一点,我们需要说服自己(或证明)基本情况总是在某个时刻被击中.

让我们假设,n < k在某些时候.因为根据我们的假设,n最初大于或等于k,必然存在某些点n = k,因为n并且k一致地n减少或仅减少一个,即它遵循

这意味着,必须subset(n - 1, k)要求它发生,并n在下面减少k.但是,这是不可能的,因为我们有一个基本情况n = k,我们返回一个常量1.

我们得出结论,要么n在某个时刻减少,要么减少n = k一致的k时间k = 0.

因此,基本情况起作用.