我在理解使用递归生成排列的代码时遇到了困难 [英] I'm having trouble understanding this code which produces permutations using recursion

问题描述

def permute2(seq):
    if not seq:                           # Shuffle any sequence: generator
        yield seq                         # Empty sequence
    else:
        for i in range(len(seq)):
            rest = seq[:i] + seq[i+1:]        # Delete current node
            for x in permute2(rest):          # Permute the others
                # In some cases x = empty string
                yield seq[i:i+1] + x          # Add node at front

for x in permute2('abc'):
    print('result =',x)

当产生第一个结果('abc')时，i == 0和seq == 'abc'的值。然后，控制流将其带到外部循环的顶部，其中i == 1是有意义的；然而，seq == 'bc'，这完全让我感到困惑。

推荐答案

我将尝试从归纳的角度对其进行解释。

设序列的长度为n。 我们的基本情况是n=0，此时我们只返回空序列(它是唯一的排列)。

如果n&>0，则： 要定义排列，我们必须首先选择第一个元素。要定义所有排列，显然我们必须将序列的所有元素视为可能的第一个元素。

选择第一个元素后，现在需要选择其余元素。但这与找出没有我们选择的元素的序列的所有排列是一样的。这个新序列的长度是n-1，所以我们可以用归纳法来求解它。

稍微修改一下原始代码，模仿我的解释，希望让它更清楚：

def permute2(seq):
    length = len(seq)
    if (len == 0):
        # This is our base case, the empty sequence, with only one possible permutation.
        yield seq
        return

    for i in range(length):
        # We take the ith element as the first element of our permutation.
        first_element_as_single_element_collection = seq[i:i+1]
        # Note other_elements has len(other_elements) == len(seq) - 1
        other_elements = seq[:i] + seq[i+1:]
        for permutation_of_smaller_collection in permute2(other_elements):
            yield first_element_as_single_element_collection + permutation

for x in permute2('abc'):
    print('result =',x)

希望可以清楚地看到，原始代码的功能与上面的代码完全相同。

这篇关于我在理解使用递归生成排列的代码时遇到了困难的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！