Question:Input a list L (without repeated elements) and output the full permutation of L.
As entered:L=[1,2,3]
Then output:[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
Full arrangement of the problem, you can use the backtracking method to solve the detailed analysis, please refer to the East public number: labuladong, read the enlightenment.
First post a correct solution:
'''
Backtracking algorithm template:
from: labuladong public
result = []
def backtrack(picklist,path):
if end condition is satisfied:
(path)
return
for Selection in Selection List:: for Selection in Selection List: for Selection in Selection List: for Selection in Selection List
Do the selection (to de-emphasize, determine whether the selection is already in the selection list, don't select the one that has already been selected)
backtrack(list of choices, path)
selection list.removelast() # Undo this selection as to start from the beginning again (backtracking to the heel node of the tree)
'''
import copy
def backtrack(L,path):
if len(path)==len(L):
c = (path) # Note that instead of adding the path directly to the res, a deep copy of the object is made here
(c)
# (path)
# print(res)
return
for i in L:
if i in path:
continue
else:
(i)
backtrack(L,path)
#path = path[:-1]
() # Note the method of "undoing" the selection here.
if __name__ == '__main__':
res = []
L = [1,2,3]
backtrack(L,[])
print(res)Output:
The above algorithm usespythonWhat happens if you don't use the deep copy of the
Look at the code below:
def backtrack(L,path): if len(path)==len(L): # c = (path) # (c) (path) print(res) return for i in L: if i in path: continue else: (i) backtrack(L,path) #path = path[:-1] () # Note the method of "undoing" the selection here. if __name__ == '__main__': res = [] L = [1,2,3] backtrack(L,[]) print(res)
Output at this time:
This is a very puzzling result, but after analyzing it more closely, it turns out that python's shallow copying is to blame. When we determine that len(path) == L, we make a shallow copy ofpath appendto res, but in fact, res is just a pointer to the path, and when we "unselect" the path, i.e.()If you look closely, the first column of each output is actually a full permutation. If you look at it carefully, the first column of each output is just about fully aligned.
See another example of an error that doesn't apply when undoing a selection()Ratherpath = path[:-1]。
import copy def backtrack(L,path): if len(path)==len(L): c = (path) # Note that instead of adding the path directly to the res, a deep copy of the object is made here (c) # (path) print(res) return for i in L: if i in path: continue else: (i) backtrack(L,path) path = path[:-1] # A different way to "undo" a selection #() # Note the method of "undoing" the selection here. if __name__ == '__main__': res = [] L = [1,2,3] backtrack(L,[]) print(res)
Output at this time:
Even more puzzling, the use ofdebugDebugging revealed that the path undo selection, thepath = path[:-1]didn't work, and in backtracking upwards, since the function signature was
backtrack(L,path)
Since path is passed into the function as a parameter, the path used should be the same one in each level of recursive calls when we use the()When unselecting, path should change at the same time in each level of the recursion stack. (As an analogy, when I recursed upwards after the first round of recursion, path = [1,2,3], reasonable thinking would have changed path to [1,2], [1] in turn, so that I could continue to add elements to it to form different permutations.) However, using path = path[:-1], debugging reveals that, except for this level of the recursion stack, the path of the recursion stacks did not changed:
This time it's a deep-copy pot, and we have a reasonable suspicion that path=path[:-1], which should generate a new object, i.e., = the left and right paths aren't the same object, so the path doesn't change at each level of the recursive tree.to verify it:
To this point this article on python backtracking algorithm to achieve the full arrangement of small exercises to share the article is introduced to this, more related python backtracking algorithm to achieve the full arrangement of content, please search for my previous articles or continue to browse the following related articles I hope that you will support me more in the future!