Нерекурсивная перестановка Python

Question

Кто-нибудь понимает следующий итерационный алгоритм для создания всех перестановок списка чисел?

Я не понимаю логику в цикле while len(stack). Может кто-нибудь объяснить, как это работает?

# Non-Recursion 
@param nums: A list of Integers. 
@return: A list of permutations. 

def permute(self, nums): 
    if nums is None: 
     return [] 
    nums = sorted(nums) 
    permutation = [] 
    stack = [-1] 
    permutations = [] 
    while len(stack): 
     index = stack.pop() 
     index += 1 
     while index < len(nums): 
      if nums[index] not in permutation: 
       break 
      index += 1 
     else: 
      if len(permutation): 
       permutation.pop() 
      continue 

     stack.append(index) 
     stack.append(-1) 
     permutation.append(nums[index]) 
     if len(permutation) == len(nums): 
      permutations.append(list(permutation)) 
    return permutations 

Я просто пытаюсь понять приведенный выше код.

Answer 1

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

Прежде всего, хотя рекурсивных вызовов функции не существует, код, который вы предоставили, является рекурсивным, поскольку все, что он делает, это сохранить свой собственный стек, вместо того, чтобы использовать тот, который предоставляется менеджером памяти вашей ОС , В частности, стек переменных хранит «рекурсивные данные», так сказать, которые передаются от одного рекурсивного вызова другому. Вы могли бы и, возможно, должны рассмотреть каждую итерацию внешнего цикла while в функции в качестве рекурсивного вызова в качестве функции. Если вы это сделаете, вы увидите, что внешний цикл while помогает «рекурсивно» пересекать каждую перестановку nums в глубину в первом порядке.

Заметив это, довольно легко понять, что делает каждый «рекурсивный вызов». В основном, переменная перестановка сохраняет текущую перестановку nums, которая формируется как цикл while. Переменная перестановки хранить все перестановки nums, которые находятся. Как вы можете заметить, перестановки обновляются, только если len (перестановка) равен len (nums), который можно рассматривать как базовый случай отношения повторения, которое реализуется с использованием пользовательского стека. Наконец, внутренний цикл while в основном выбирает, какой элемент nums, чтобы добавить в текущую перестановку (т. Е. Сохраненную в переменной перестановку).

Так вот об этом, действительно. Вы можете выяснить, что именно делается на линиях, относящихся к обслуживанию стек с использованием отладчика, как это было предложено. В качестве заключительного замечания позвольте мне повторить, что я лично не считаю эту реализацию нерекурсивной. Так получилось, что вместо использования абстракции, предоставляемой ОС, это рекурсивное решение сохраняет свой собственный стек. Чтобы лучше понять, каким будет правильное нерекурсивное решение, вы можете увидеть разницу в рекурсивных и итеративных решениях проблемы поиска n ^th Число Фибоначчи, представленное ниже. Как вы можете видеть, нерекурсивное решение не содержит стека, и вместо того, чтобы делить проблему на более мелкие экземпляры (рекурсия), она создает решение из меньших решений. (Динамическое программирование)

def recursive_fib(n): 
    if n == 0: 
     return 0 
    return recursive_fib(n-1) - recursive_fib(n-2) 

def iterative_fib(n): 
    f_0 = 0 
    f_1 = 1 
    for i in range(3, n): 
     f_2 = f_1 + f_0 
     f_0 = f_1 
     f_1 = f_2 
    return f_1 

Answer 2

Ответ от @ilim правильно и должен быть принятый ответ, но я просто хотел бы добавить еще один момент, который не соответствовал бы как комментарий.В то время как я полагаю, вы изучаете этот алгоритм в качестве упражнения следует отметить, что лучший способ продолжить, в зависимости от размера списка, может быть пользователем itertools «s permutations() функции:

print [x for x in itertools.permutations([1, 2, 3])] 

Тестирование на моя машина со списком из 11 пунктов (39 м перестановки) заняла 1.7 сек. с itertools.permutations(x), но взяла 76 сек., используя указанное выше решение. Обратите внимание, однако, что с 12 элементами (479 м перестановки) решение itertools взрывается с ошибкой памяти. Если вам нужно генерировать перестановки такого размера эффективно, вы можете лучше отказаться от собственного кода.