1

我正在阅读 NLP with Python 这本书，我从“高级”部分遇到了这个例子。我很感激帮助理解它是如何工作的。该函数计算多个音节达到“米”长度 n 的所有可能性。短音节“S”占一个单位长度，而长音节“L”占两个单位长度。因此，对于 4 米的长度，return 语句如下所示：

['SSSS', 'SSL', 'SLS', 'LSS', 'LL']

功能：

def virahanka1(n):
    if n == 0:
        return [""]
    elif n == 1:
        return ["S"]
    else:
        s = ["S" + prosody for prosody in virahanka1(n-1)]
        l = ["L" + prosody for prosody in virahanka1(n-2)]
        return s + l

如果 s 和 l 是单独的列表，我不明白的部分是如何进行“SSL”、“SLS”和“LSS”匹配。同样在“virahanka1(n-1) 中的韵律”这一行中，什么是韵律？它是函数每次返回的内容吗？我试图一步一步地思考它，但我没有得到任何地方。在此先感谢您的帮助！

阿德里安

4

3 回答 3

2

让我们从头开始构建函数。这是彻底理解它的好方法。

假设我们想要一个递归函数来枚举 Ls 和 Ss 的每个组合以生成给定的米长n。让我们考虑一些简单的案例：

  • n = 0：唯一的方法是使用空字符串。
  • n = 1：唯一的方法是使用单个 S。
  • n = 2：你可以用一个 L 或两个 S 来做到这一点。
  • n = 3：LS、SL、SSS。

现在，考虑一下如何n = 4根据上述数据构建答案。嗯，答案将涉及将 S 添加到 3 米长，或者将 L 添加到 2 米长。因此，在这种情况下，答案将是LL, LSS从 n = 2 和SLS, SSL, SSSS从n = 3。您可以检查这是所有可能的组合。我们也可以看到，n = 2并且n = 3可以类似地从 n = 0,1 和 n=1,2 获得，因此我们不需要对它们进行特殊处理。

通常，对于，您可以通过查看长度和长度n ≥ 2的字符串来导出长度的字符串。nn-1n-2

那么，答案就很明显了：

  • 如果 n = 0，则只返回一个空字符串
  • 如果 n = 1，则返回单个 S
  • 否则，返回对所有米长字符串添加 S 的结果，以及向所有n-1米长字符串添加 L 的结果n-2。

顺便说一句，编写的函数效率有点低，因为它重新计算了很多值。如果您要求例如，那将使其非常慢n = 30。lru_cache您可以使用Python 3.3中的新功能非常轻松地使其更快：

@lru_cache(maxsize=None)
def virahanka1(n):
    ...

这会缓存每个 的结果n，使其更快。

于 2013-08-03T03:32:34.737 回答
1

我试图融化我的大脑。我添加了打印语句来向我解释发生了什么。我认为递归调用最令人困惑的部分是它似乎进入了前向调用但向后退出，正如您在运行以下代码时所看到的那样；

def virahanka1(n):
    if n == 4:
            print 'Lets Begin for ', n
    else:
            print 'recursive call for ', n, '\n'
    if n == 0:
        print 'n = 0 so adding "" to below'
        return [""]
    elif n == 1:
        print 'n = 1 so returning S for below'
        return ["S"]
    else:
        print 'next recursivly call ' + str(n) + '-1 for S'
        s = ["S" + prosody for prosody in virahanka1(n-1)]
        print '"S" + each string in s equals', s
        if n == 4:
            print '**Above is the result for s**'
        print 'n =',n,'\n', 'next recursivly call ' + str(n) + '-2 for L'
        l = ["L" + prosody for prosody in virahanka1(n-2)]
        print '\t','what was returned + each string in l now equals', l
        if n == 4:
            print '**Above is the result for l**','\n','**Below is the end result of s + l**'
        print 'returning s + l',s+l,'for below', '\n','='*70
        return s + l
virahanka1(4)

仍然让我感到困惑，但有了这个和 Jocke 的优雅解释，我想我可以理解发生了什么。

你呢？

以下是上面的代码产生的内容；

Lets Begin for  4
next recursivly call 4-1 for S
recursive call for  3

next recursivly call 3-1 for S
recursive call for  2

next recursivly call 2-1 for S
recursive call for  1

n = 1 so returning S for below
"S" + each string in s equals ['SS']
n = 2
next recursivly call 2-2 for L
recursive call for  0

n = 0 so adding "" to below
        what was returned + each string in l now equals ['L']
returning s + l ['SS', 'L'] for below
======================================================================
"S" + each string in s equals ['SSS', 'SL']
n = 3
next recursivly call 3-2 for L
recursive call for  1

n = 1 so returning S for below
        what was returned + each string in l now equals ['LS']
returning s + l ['SSS', 'SL', 'LS'] for below
======================================================================
"S" + each string in s equals ['SSSS', 'SSL', 'SLS']
**Above is the result for s**
n = 4
next recursivly call 4-2 for L
recursive call for  2

next recursivly call 2-1 for S
recursive call for  1

n = 1 so returning S for below
"S" + each string in s equals ['SS']
n = 2
next recursivly call 2-2 for L
recursive call for  0

n = 0 so adding "" to below
        what was returned + each string in l now equals ['L']
returning s + l ['SS', 'L'] for below
======================================================================
        what was returned + each string in l now equals ['LSS', 'LL']
**Above is the result for l**
**Below is the end result of s + l**
returning s + l ['SSSS', 'SSL', 'SLS', 'LSS', 'LL'] for below
======================================================================
于 2013-08-03T03:35:26.897 回答
0

这个函数说：

virakhanka1(n)与[""]whenn为零，["S"]whenn为 1，s + l否则相同。wheres与 的结果"S"列表中的每个元素的前置结果相同virahanka1(n - 1)，并且与的元素的前置l相同。"L"virahanka1(n - 2)

所以计算将是：

When n is 0:
    [""]
When n is 1:
    ["S"]
When n is 2:
    s = ["S" + "S"]
    l = ["L" + ""]
    s + l = ["SS", "L"]
When n is 3:
    s = ["S" + "SS", "S" + "L"]
    l = ["L" + "S"]
    s + l = ["SSS", "SL", "LS"]
When n is 4:
    s = ["S" + "SSS", "S" + "SL", "S" + "LS"]
    l = ["L" + "SS", "L" + "L"]
    s + l = ['SSSS", "SSL", "SLS", "LSS", "LL"]

你有它，一步一步。

您需要知道其他函数调用的结果才能计算最终值，如您所见，手动执行可能会非常麻烦。重要的是不要尝试在脑海中递归地思考。这会让你的思想融化。我用文字描述了函数，所以你可以看到这些函数是描述，而不是命令序列。

您看到的prosody，即定义的一部分s，l是变量。它们用于列表理解，这是一种构建列表的方式。我之前已经描述了这个列表是如何构建的。

于 2013-08-03T03:03:20.937 回答