Примеры, представленные здесь, несколько усложняют отслеживание рекурсивных шаблонов, которые вы обсуждаете, но ваша интуиция в отношении ссылок в основном верна.
В общем, при обходе дерева вызовов, такого как этот, с использованием спискаВ качестве параметра для рекурсивной функции существует два подхода.Первый - передать копию списка, который иллюстрирует ваш первый пример (с использованием синтаксиса slice [:], который создает копию всего списка).
ВторойПодход заключается в том, чтобы никогда не копировать список и разрешить функциям в стеке вызовов обращаться к одному и тому же списку в течение всего обхода.Этот подход требует восстановления состояния списка после разрешения каждого вызова.Мы должны сделать это для того, чтобы сохранить логику копии, не давая мутациям дочерних узлов изменять родительское состояние.
Вот быстрая перезапись примера функции, которую вы предоставили для соблюдения PEP8 и удаляет бесполезную строку (listC = listB;):
def foo(n, lst):
if n:
lst.append(n)
foo(n - 1, lst[:])
print(f"n: {n}, lst: {lst}, id: {id(lst)}")
if __name__ == "__main__":
foo(4, [])
Вывод:
n: 1, lst: [4, 3, 2, 1], id: 140439070012752
n: 2, lst: [4, 3, 2], id: 140439070012832
n: 3, lst: [4, 3], id: 140439139990576
n: 4, lst: [4], id: 140439072829760
Обратите внимание, что распечатки происходят после разрешения рекурсивных вызовов, поэтому мы видим полностью заполненныйсписок в окончательном вызове печати в первую очередь.Переставьте функцию для печати в первую очередь, если это сбивает с толку - местоположение не имеет значения.Важной частью является то, что в каждом списке имеется совершенно отдельный идентификатор, поэтому мы создали в общей сложности 4 списка.
Теперь вот эквивалентная версия (с точки зрения вывода), которая использует только один список за все времяи использует описанную выше технику «восстановления состояния»:
def bar(n, lst):
if n:
lst.append(n)
bar(n - 1, lst)
print(f"n: {n}, lst: {lst}, id: {id(lst)}")
lst.pop() # undo the append to restore state in this frame
if __name__ == "__main__":
bar(4, [])
Вывод:
n: 1, lst: [4, 3, 2, 1], id: 139793013186800
n: 2, lst: [4, 3, 2], id: 139793013186800
n: 3, lst: [4, 3], id: 139793013186800
n: 4, lst: [4], id: 139793013186800
Обратите внимание на несколько вещей.Во-первых, логический вывод тот же.Убедитесь сами, что каждый append сопровождается pop, который полностью восстанавливает состояние для родительского вызова, отменяя все мутации, выполненные в текущем кадре стека.Во-вторых, обратите внимание, что у нас есть один список за все время с идентификатором 139793013186800.
Имейте в виду, что в рекурсивном стеке вызовов родительские вызовы удерживаются до тех пор, пока все дочерние элементы не разрешат полностью ,поэтому нам нужно только беспокоиться о состоянии текущего кадра.
Теперь, когда мы увидели теорию, давайте рассмотрим две версии метода перестановок:
def print_permute_copy(lst, i=0):
if i == len(lst):
print("".join(lst))
else:
for j in range(i, len(lst)):
cpy = lst[:]
cpy[i], cpy[j] = cpy[j], cpy[i]
print_permute_copy(cpy, i + 1)
def print_permute_restore(lst, i=0):
if i == len(lst):
print("".join(lst))
else:
for j in range(i, len(lst)):
lst[i], lst[j] = lst[j], lst[i]
print_permute_restore(lst, i + 1)
lst[i], lst[j] = lst[j], lst[i]
if __name__ == "__main__":
print_permute_copy(list("abc"))
print()
print_permute_restore(list("abc"))
Вывод:
abc
acb
bac
bca
cba
cab
abc
acb
bac
bca
cba
cab
Мы видим, что оба верны и дают эквивалентный вывод.Функция top создает новые копии списка для передачи детям.При этом ему не нужно беспокоиться о восстановлении своего состояния после того, как список будет возвращен дочерними элементами.Недостатком этого подхода является необходимость создания нового списка для каждого вызова, что неэффективно.
С другой стороны, версия для восстановления просто передает один список и выполняет все операции с ним.После выполнения свопинга он передает мутировавший список своим дочерним элементам, которые также выполняют свопы, но каждый отменяет любые свопы, которые он выполняет, когда его дочерние элементы работают со списком (и в конечном итоге отменяют свои свопы).
Код, который вы показали, имеет гораздо более сложное состояние, но давайте рассмотрим этот фрагмент:
for i in range(len(uniqueChar)):
if (countArray[i]!=0):
result.append(uniqueChar[i])
countArray[i] = countArray[i]-1;
level = level + 1;
getPerm(uniqueChar, countArray[:], result[:], level, lenOrigString)
level = level -1;
Попытка использования нарезки не удалась, потому что countArray[i] = countArray[i]-1 (более ясно, как countArray[i] -= 1) не выполняется для копии, но в родительском списке.То же самое для result.append(uniqueChar[i]) - это должно быть выполнено для копии, которую мы готовим передать ребенку, а не для списка родителей.
Это работает:
for i in range(len(uniqueChar)):
if countArray[i] != 0:
cpy = countArray[:]
cpy[i] = cpy[i] - 1;
level = level + 1;
getPerm(uniqueChar, cpy, result + [uniqueChar[i]], level, lenOrigString)
level = level -1;
Обратите внимание, что это менее эффективно, чем подход "восстановление состояния" в оригинале, поэтому я показываю его исключительно в демонстрационных целях.Также обратите внимание, что result + [uniqueChar[i]] использует конкатенацию списков и создает новый список с добавленным новым элементом.Количество копий всех этих списков увеличивается по мере увеличения длины строки (временная сложность O (N!)).
Для полноты картины обратите внимание, что эту функцию можно записать просто как list(itertools.permutations(iterable)).Даже если вы решите написать это от руки для образовательных целей, таких как этот, есть намного более простые алгоритмы, чем предоставленный, который использует много дополнительного состояния и трудно рассуждать из-за повторяющегося кода getPerm is практически дословно повторяется внутри printPermutations.Частично проблема заключается в том, что Java является гораздо более многословным языком, чем Python, с очень разными операциями и структурами, поэтому буквальный перевод кода Java почти гарантированно не является Pythonic.
Некоторые предложения по присоединению к Pythonстиль более точно:
snake_case для переменных и функций. if(foo==bar): должен быть записан как if foo == bar: (использует пробелы вокруг операторов, пропускает ненужные скобки). foo=foo+1 яснее как foo += 1 (оператор приращения, пробел вокруг операторов). result.pop(len(result)-1) яснее как result.pop(). - Нет необходимости использоватьвведите имена переменных.В Python нет массивов, поэтому
countArray может быть counts, charArray может быть characters и т. Д. (Множественное число - хороший способ обозначать списки). - Точки с запятой не нужны.
Используйте вертикальные пробелы вокруг операторов блока:
countArray = [];
for iChar in range(26):
должно быть
counts = []
for i in range(26):
Избегать функций, которые создают побочные эффекты и предпочитают возвращать генераторы , следующие itertools:
def permute(lst, i=0):
if i == len(lst):
yield lst[:]
else:
for j in range(i, len(lst)):
lst[i], lst[j] = lst[j], lst[i]
yield from permute(lst, i + 1)
lst[i], lst[j] = lst[j], lst[i]
if __name__ == "__main__":
print(list(permute(list("abc"))))