Как работает мое решение для рекурсивного генерирования всех перестановок строки? - PullRequest
Новая
       8

Как работает мое решение для рекурсивного генерирования всех перестановок строки?

0 голосов
/ 20 ноября 2018 
def permutationString(word):
    print('word', word)
    result = []

    if len(word) == 0:
        result.append('')
        return result

    for i in range(len(word)):
        before = word[0 : i]
        after = word[i + 1 :]
        print('before',before)
        print('after', after)
        partials = permutationString(before + after)
        print(partials)
        for s in partials:
            result.append(word[i] + s)

    return result

Это мое решение для генерации перестановки для данной строки.

Для ввода abc он дает мне ['abc', 'acb', 'bac', 'bca', 'cab', 'cba'], что кажется правильным.

У меня вопрос, я не очень понимаю, как работает магия.Сам код довольно интуитивно понятен;мы просто пытаемся каждый символ в качестве первого символа, а затем добавляем перестановки.

Но я действительно не понимаю, как генерируется partials, и я не уверен, как решение не работает, когда мы не делаемделать result.append(''), когда word пусто.

Есть ли интуитивное объяснение того, как работает магия?

1 Ответ

0 голосов
/ 20 ноября 2018

У меня есть полный ответ здесь .

Короче, ответ заключается в том, что есть только один способ написать последовательность без элементов. Это пустая последовательность. Таким образом, список со всеми перестановками '' равен [''].

Предположим, вы ошиблись и вернули [] вместо этого, то есть никаких решений. Что будет потом?

Что ж, в индуктивном случае, как вы сказали, вы пробуете каждый элемент как первый и ставите его перед решениями для перестановок без этого элемента. Итак, рассмотрим последовательность только с одним элементом 'x'. Вы собираетесь поставить x перед всеми решениями для ''. Если перестановки '' вернули [], то есть пустой список без решений, то у вас не было бы решений, чтобы поставить x перед. Он возвращает [''], поэтому вы поставите 'x' перед этим единственным решением ''.

Бонус

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

Попробуйте построить все перестановки word, выбрав только первый элемент word[0] на каждом рекурсивном шаге и каким-то образом "комбинируя" его с решениями для перестановок word[1:].

...