Python 字符串递归，字符串索引超出范围

Question

我是 python 的新手，非常不擅长以递归方式思考。这段代码给我一个 IndexError: string index out of range。而且我不知道如何纠正它。

def get_permutations(sequence):

    def permutationhelp(sequence,chosen):

        if sequence=="":
            print(chosen)

        else:

            for i in range(len(sequence)):
                c= sequence[i]
                chosen +=c
                sequence=sequence[i+1:]
                permutationhelp(sequence,chosen)
                sequence=c+sequence
                chosen=chosen[:-1]

    def permutation(sequence):
        permutationhelp(sequence,"")


    return permutation(sequence)

例子:

get_permutations('abc')
['abc', 'acb', 'bac', 'bca', 'cab', 'cba']

回溯是这样的:

Traceback (most recent call last):
  File "soRecursivePermutations.py", line 25, in <module>
    get_permutations('abc')
  File "soRecursivePermutations.py", line 23, in get_permutations
    return permutation(sequence)
  File "soRecursivePermutations.py", line 20, in permutation
    permutationhelp(sequence,"")
  File "soRecursivePermutations.py", line 12, in permutationhelp
    c= sequence[i]
IndexError: string index out of range

Answer 1

Traceback 的原因在这里:

sequence=sequence[i+1:]
permutationhelp(sequence,chosen)
sequence=c+sequence

第一行将 sequence 留在字符串的末尾。第三行只将一个字符添加回 sequence，因此 sequence 会随着循环变短。

但是，这可能是您正在寻找的程序:

# https://stackoverflow.com/a/53088155/4834
def remove_at(i, s):
    return s[:i] + s[i + 1:]

def permutationhelp(sequence, chosen, collect):
    if sequence == "":
        collect.append(chosen)
    else:
        for i,c in enumerate(sequence):
            permutationhelp(remove_at(i, sequence), chosen + c, collect)

def get_permutations(sequence):
    collect = []
    permutationhelp(sequence, "", collect)
    return collect

print(get_permutations('abc'))

输出:

['abc', 'acb', 'bac', 'bca', 'cab', 'cba']