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

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)

希望很清楚原始代码与上面的代码执行完全相同的操作。