我在理解使用递归生成排列的代码时遇到了困难

问题描述

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)

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