Рекурсия строки 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 это:

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

Причина вашего отслеживания здесь:

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

Answer 2

Следует настоятельно рекомендовать использовать:

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 3

@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)

TestCase

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

Answer 4

Мне пришлось скопировать его, чтобы выяснить проблему, исключение ясно говорит о том, что вы пытались получить доступ к индексу, который длиннее предоставленного массива.

Я немного отредактировал в вашем решении.

1. Я остановил "выбранную" переменную опоры в рекурсии

2. Я заставил ее вернуть список результатов.

   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

Я думаю, вы можете подойти к этому по-другому.Следуя вашему коду, я думаю, что вы просто хотите сократить список и распечатать результат на консоли, когда вы исчерпали последовательность, но я не вижу никакой логики для реальной перестановки.Прости меня, если он там и я пропустил это.

Вот как я об этом думаю.Начните с первого элемента «a», сохраните индекс «i», чтобы передать его в вашу вспомогательную функцию, затем поменяйте местами со списком, который не содержит «a», поэтому в этом случае это будут «b и c».Затем сопоставьте это с вашим индексом "i" и снова отмените список с тем же самым символом.Это выведет «abc and acb».

Затем я увеличу «i» и снова вызову вашего помощника.Итак, теперь ваш элемент - «b», а список подкачки - «a и c», и выдает «bac» и «bca».Затем увеличьте и повторите снова, чтобы получить «cab» и «cba».Вы можете иметь свой базовый случай рекурсии, так как я такой же, как len (последовательность).Надеюсь, я никуда тебя не потерял.Я не кодировал это, потому что понял, что ты пытаешься учиться на практикеУдачи!