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

应强烈考虑使用：

import itertools

for p in itertools.permutations("abc"):
    print(''.join(p))
# abc
# acb
# bac
# bca
# cab
# cba

或者如果您想存储在 list 中：

perm = [''.join(p) for p in itertools.permutations('abc')]

Answer 2

你回溯的原因在这里：

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

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

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

# 
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']

Answer 3

我认为您可能希望采用不同的方法。根据您的代码，我认为您只是想减少列表并在运行乱序时将结果打印到控制台，但我没有看到任何实际排列的逻辑。如果它在那里而我错过了，请原谅我。

这是我的看法。从第一个元素 "a" 开始，保留索引 "i" 以将其传递给您的辅助函数，然后与不包含 "a" 的列表进行交换，因此在这种情况下它将是 "b and c." 然后将其与您的 "i" 索引字符连接起来，并再次取消交换具有相同字符的列表。这将打印出 "abc and acb."

然后我会增加 "i" 并再次呼叫您的助手。所以现在你的元素是 "b" 并且交换列表是 "a and c" 并产生 "bac" 和 "bca"。然后递增并再次重复，产生 "cab" 和 "cba"。你可以有你的递归基本情况，因为 i 与 len(sequence) 相同。希望我没有在任何地方失去你。我没有编写代码，因为我认为您正在尝试边做边学。祝你好运！

Answer 4

我不得不复制它来找出问题所在，异常清楚地表明您正在尝试访问比提供的数组更长的索引。

我在您的解决方案中编辑了一些内容。

我在递归中停止了"chosen"变量依赖

我把它设为 return 结果列表。

def get_permutations(sequence):

 def permutationhelp(sequence):
   if len(sequence) == 1:
    return sequence
result = []
for i in range(len(sequence)):
    c = sequence[i]
    remaining = sequence[:i] + sequence[i+1:]
    for perm in permutationhelp(remaining):
        result.append(c + perm)

return result

def permutation(sequence):
  result = permutationhelp(sequence)
  print(result)


return permutation(sequence)

get_permutations('abc')

结果：

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

Answer 5

@quamrana给了很好的解释。这里我觉得下面的代码更有助于OP理解他的错误和递归算法

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] + sequence[i+1:]
                permutationhelp(sequence,chosen)
                sequence = sequence[:i] + c + sequence[i:]
                chosen = chosen[:-1]

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

    return permutation(sequence)

测试用例

>>> get_permutations('abc')
abc
acb
bac
bca
cab
cba

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

Python string recursion, string index out of range

python

string

recursion

index-error