Помогите понять, как работает эта рекурсивная функция python?

Question

Я программист, я делаю некоторые C # Perl и Python, в любом случае, я нашел этот рекурсивный код для генерации перестановок, из списка символов и букв, но я не могу понять, как это работает?кто-нибудь может объяснить это, пожалуйста?

#!/usr/bin/env python
#-*- coding:utf-8 -*-

def generate(charlist,state,position):
    for i in charlist:
        state[position] = i
        if position == (len(state)-1):
            print "".join(state)
        else:
            generate(charlist,state,position+1)

generate("1234567890qwertyuiopasdfghjklzxcvbnm",[None]*8,0)

вот код, со всеми правильными интервалами.

Answer 1

Это не генерирует перестановки. Генерирует n-мерные декартовы произведения. (При этом он также генерирует все перестановки, но алгоритм генерации только перестановок будет другим.)

Немного сложно объяснить, как это работает, но если вы посмотрите на вывод для небольшого ввода, вы сможете увидеть, что происходит. Рассмотрим выходные данные для 'abc' и [None] * 3 (я изменил код, чтобы он действовал как настоящий генератор):

>>> def generate(charlist,state,position):
...     for i in charlist:
...         state[position] = i
...         if position == (len(state)-1):
...             yield "".join(state)
...         else:
...             for j in generate(charlist,state,position+1):
...                 yield j
... 
>>> print list(generate('abc', [None] * 3, 0))
['aaa', 'aab', 'aac', 'aba', 'abb', 'abc', 'aca', 'acb', 'acc', 
 'baa', 'bab', 'bac', 'bba', 'bbb', 'bbc', 'bca', 'bcb', 'bcc', 
 'caa', 'cab', 'cac', 'cba', 'cbb', 'cbc', 'cca', 'ccb', 'ccc']

Как видите, вначале generate вызывает себя три раза, увеличивая position каждый раз (с 0 до 1 до 2). Каждый раз в цикле рекурсии он помещает 'a' в текущую позицию и проверяет, достиг ли он конца списка state. Если это так, он дает результат и не вызывает себя.

В этом случае, когда это произойдет, position == 2. Теперь включается цикл for, сохраняя 'b' и 'c' в state[2] и приводя к каждому из этих состояний. Затем функция завершается, и управление возвращается вызывающей стороне, для чего position == 1. Вызывающий затем продолжает цикл for; он устанавливает state[1] = 'b', а затем, поскольку position больше не находится в конце списка state, он снова вызывает себя ... теперь position == 2 и наборы циклов for state[2] == 'a', 'b', 'c' и т. Д.

Кстати, если вы хотите вычислить декартовы произведения в python, вот хороший способ, который не требует от ваших читателей разбора рекурсивного алгоритма:

>>> import itertools
>>> [''.join(c) for c in itertools.product('abc', 'abc', 'abc')]
['aaa', 'aab', 'aac', 'aba', 'abb', 'abc', 'aca', 'acb', 'acc', 
 'baa', 'bab', 'bac', 'bba', 'bbb', 'bbc', 'bca', 'bcb', 'bcc', 
 'caa', 'cab', 'cac', 'cba', 'cbb', 'cbc', 'cca', 'ccb', 'ccc']

Вы могли бы также сделать

>>> [''.join(c) for c in itertools.product(*['abc'] * 3)]

Answer 2

Вы не можете понять, как это работает?Поместите эту строку сразу после def generate...:

print charlist, state, position

, и она сообщит вам, какие переменные используются при каждом вызове.

Answer 3

Функция выводит каждую возможную (если не третий аргумент ненулевой) комбинацию заданных символов.

Он принимает в качестве ввода:

1. список или строка символов, которые будут объединены,
2. список, длина которого обозначает, сколько символов следует объединить одновременно,
3. число, обозначающее, сколько символов каждой комбинации следует заменить соответствующими символами из второго списка (что соответственно уменьшит количество возможных комбинаций).

Если второй аргумент является списком из 8 None значений (потому что [None] * 8 == [None, None, None, None, None, None, None, None]), установка третьего аргумента в ненулевое значение приведет к TypeError.

@ ответ отправителя объясняет, что происходит в функции.

Я должен сказать, что это пример непифонического кода именно потому, что трудно понять его назначение с первого взгляда.