关于使用递归进行字符串排列的问题

Question

这与递归有关。s是字符串“abc”。你知道吗

返回s的所有排列。因此所需的输出是：['abc'、'acb'、'bac'、'bca'、'cab'、'cba']。 但我无法理解下面代码中的行：

"for perm in permute(s[:i] + s[i+1:]):"

在"s[:i] + s[i+1:]"的第一个print语句中，它打印出“c”，而不是“bc”。我认为，由于索引I从0开始（其中I=0，let=“a”），“s[：0]+s[o+1:]”将变成s[1:]

它应该返回“bc”，因为“b”在索引1处，c是最后一个字母。但是print语句返回“c”。你知道吗

def permute(s):
    out = []

    # Base Case
    if len(s) == 1:
        out = [s]

    else:
        # For every letter in string
        for i, let in enumerate(s):

            # For every permutation resulting from Step 2 and 3 described above
            for perm in permute(s[:i] + s[i+1:]):
                print('s is ' + s)
                print('s[:i] + s[i+1:] is ' + str(s[:i] + s[i+1:]))
                print('i is ' + str(i))
                print('Current letter is ' + let)
                print('Current perm is ' + perm)

                # Add it to output
                out += [let + perm]
                print('out is ' + str(out))
                print()

    return out          

permute('abc')

s is bc
s[:i] + s[i+1:] is c
i is 0
Current letter is b
Current perm is c
out is ['bc']

s is bc
s[:i] + s[i+1:] is b
i is 1
Current letter is c
Current perm is b
out is ['bc', 'cb']

s is abc
s[:i] + s[i+1:] is bc
i is 0
Current letter is a
Current perm is bc
out is ['abc']

s is abc
s[:i] + s[i+1:] is bc
i is 0
Current letter is a
Current perm is cb
out is ['abc', 'acb']

s is ac
s[:i] + s[i+1:] is c
i is 0
Current letter is a
Current perm is c
out is ['ac']

s is ac
s[:i] + s[i+1:] is a
i is 1
Current letter is c
Current perm is a
out is ['ac', 'ca']

s is abc
s[:i] + s[i+1:] is ac
i is 1
Current letter is b
Current perm is ac
out is ['abc', 'acb', 'bac']

s is abc
s[:i] + s[i+1:] is ac
i is 1
Current letter is b
Current perm is ca
out is ['abc', 'acb', 'bac', 'bca']

s is ab
s[:i] + s[i+1:] is b
i is 0
Current letter is a
Current perm is b
out is ['ab']

s is ab
s[:i] + s[i+1:] is a
i is 1
Current letter is b
Current perm is a
out is ['ab', 'ba']

s is abc
s[:i] + s[i+1:] is ab
i is 2
Current letter is c
Current perm is ab
out is ['abc', 'acb', 'bac', 'bca', 'cab']

s is abc
s[:i] + s[i+1:] is ab
i is 2
Current letter is c
Current perm is ba
out is ['abc', 'acb', 'bac', 'bca', 'cab', 'cba']

Answer 1

这是个很难练习的问题。所以。。。你知道吗

for i, let in enumerate(s): 为第一个值提供0 a，然后它将其传递给Permute for循环。。。你知道吗

[0a，1b，2c]这是循环中此时的值

"for perm in permute(s[:i] + s[i+1:]):

它调用函数permute（），对吗 它再次调用枚举（'bc'）0 b作为第一个值，然后将其传递给。。。排列

[0b，1c]这些是循环中此时的值

"for perm in permute(s[:i] + s[i+1:]):

看到发生什么了吗？ 它在…c！上调用函数permute（）！这正是我们试图到达的地方。 c是第一次烫发，因为它是len（s）==1，从一开始就被加到out。绝对不是一个容易的问题。 编辑：

permute函数获取字符串s，并将其分成从s开始到i索引（即s[：i]）的几部分，另一部分是s[i+1:]，即字符串末尾的i+1。所以在bc上，i是0，它取s[：0]空字符串和s[0+1:]，后者是索引1，最后是c，并在其上排列。s现在是长度1，这意味着它存储在out中。i为零abc->；bc i为零bc->；c。i为0，let=b，perm=c，当i=1时，let为c，perm=b。你知道吗

我想到了一些可以让你更好地理解这段代码的东西。你应该在这样的位置加上一个打印语句。你知道吗

    # Base Case
if len(s) == 1:
    print('Length is 1 s=',s)
    out = [s]

我认为，因为省略了这一点，所以当它到达需要调用置换的末尾时，就更难看到了。你知道吗