13

这是带有参数 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) 部分。谁能给我解释一下？

4

3 回答 3

32

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

每当您从 中选择k元素时n，都有两种情况：

  1. 你选择元素#n
  2. 你不选择元素#n

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

选择元素#n

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

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

    subset(n - 1, k - 1)

不选择元素#n

仍然有k元素可供选择，但由于我们已经决定了 element #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，即它遵循

这意味着，必须有一个要求subset(n - 1, k)它发生，n低于k。但是，这是不可能的，因为我们有一个n = k返回常量的基本情况1。

我们得出结论，要么n在某个点上减少，要么n = k一致地减少，精确k到这样k = 0。

因此，基本情况有效。

于 2012-10-20T11:19:21.937 回答
1

这更像是一个数学问题，而不是一个编程问题。你正在做的是计算二项式系数，公式是

(n, k) = (n-1, k-1) + (n-1, k) with all (n, 0) and (n, n) having a value of 1.

请在此处查看完整说明。可以在这里看到递归解决方案。如果提到的链接失效，只需使用谷歌搜索它。我怀疑你会比阅读维基百科上的这篇文章后得到更好的解释。

于 2012-10-19T09:18:31.133 回答
1

代码片段：

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

使用两个组合事实：

nC0 = 1
nCn = 1

作为基本情况。

接下来，进行递归调用：

return subset(n-1, k-1) + subset(n-1, k)

直接将以下事实转化为代码：

nCr = (n-1)C(k-1) + (n-1)Ck

如果您难以理解上述等式如何成立，请继续阅读：在 nCr 中，我们从 n 中选择 r 项。如果我们考虑任何特定项目，这些选择可以分为两个互斥的类别：

  • 项目出现在 r 个选定项目中

    在这种情况下，我们必须从剩余的 n-1 项中选择剩余的 r-1 项。这可以在 (n-1)C(k-1) 中完成。

  • 项目没有出现在 r 个选择的项目中

    在这种情况下，我们必须从剩余的 n-1 项中选择所有 r 项，这可以以 (n-1)Ck 种方式完成。

正如我已经说过的，我们将这两个相加，这两个类是互斥的，因此一起形成了从 n 中选择 r 项的全部方式。

于 2017-03-21T18:53:15.797 回答