我无法理解这段使用递归产生排列的代码

Question

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' 的值。然后控制流将其带到外部 for 循环的顶部，其中 i == 1，这是有道理的；然而，seq == 'bc'，这让我完全困惑。

Answer 1

我将尝试从归纳的角度来解释它。

令序列的长度为n。
当我们简单地返回空序列（这是唯一的排列）时，我们的基本情况是 n = 0。

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

一旦我们选择了第一个元素，我们现在需要选择其余的元素。但这与查找没有我们选择的元素的序列的所有排列相同。这个新序列的长度为n-1，因此通过归纳我们可以解决它。

稍微改变原始代码以模仿我的解释并希望使其更清晰：

def permute2(seq):
    length = len(seq)
    if (length == 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_of_smaller_collection

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

希望很明显原始代码与上述代码执行完全相同的操作。