python - 你能给我解释一下这个递归的 "n choose k"代码吗？

Question

这是带有参数 n 和 k 的子集问题的代码。 n代表学生总数，k代表我想从n中选出多少学生。该代码试图给出从 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)

我理解递归调用的第一部分，但我无法理解 + subset(n-1, k) 部分。谁能给我解释一下？

Answer 1

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

无论何时选择 k n 中的元素，有两种情况:

1. 您选择元素 #n
2. 您没有选择元素 #n

由于这些事件是互斥的，所以组合的总数由选择时的组合数量给出#n ，以及那些你不选择 #n 的人.

选择元素 #n

既然我们已经选择了一个元素，我们只需要选择另一个k-1元素。此外，由于我们已经决定了一个元素——是否包含它——我们只需要考虑剩余的 n-1。元素。

因此，选择元素的组合数量#n由

    subset(n - 1, k - 1)

不选择元素#n

还有k要选择的元素，但由于我们已经决定了元素 #n , 只剩下 n - 1可供选择的元素。因此:

    subset(n - 1, k)

基本案例

递归使用的事实是，我们通常可以区分两种情况，解决方案中元素 n是该解决方案的一部分，而那些不是。

然而，这样的区分并不总能做出:

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

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

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 .

因此，基本情况有效。