python – 你能解释一下这个递归的“n选择k”代码吗?

这是带参数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)部分.任何人都可以向我解释这个吗?

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

每当你从n中选择k个元素时,有两种情况:

>您选择元素#n
>您不选择元素#n

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

选择元素#n

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

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

subset(n - 1, k - 1)

不选择元素#n

仍然有k个元素可供选择,但由于我们已经决定了元素#n,因此只剩下n – 1个元素可供选择.从而:

subset(n - 1, k)

基本情况

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

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

>选择所有元素时(对应于下面代码中的情况n == k)
>或者根本不选择任何元素(对应于下面代码中的情况k == 0)

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

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

确保它的工作原理

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

让我们假设,n< k在某个时刻.由于根据我们的假设,n最初大于或等于k,因此n = k必然存在一些点,因为n和k一致地减少或者只有n减少1,即它遵循 这意味着必须调用子集(n-1,k)使其发生,n减小到k以下.但是,这是不可能的,因为我们在n = k上有一个基本情况,其中我们返回一个常数1. 我们得出结论,n或者n在某一点减小,使得n = k,或者一致地减少k次,使得k = 0. 因此,基本情况起作用.

相关文章
相关标签/搜索