Recently, I am studying algorithms using Python in letcode. I am studying the code to perform permutation as shown below, but there is something I don't understand in the middle.
from typing import List
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
results, prev_elements = [], []
def dfs(elements):
print(f' # elements: {elements} # prev_elements: {prev_elements}')
# Why len(elements) == 0: The length of the next_elements given by the dfs factor is leaf no\
This is because the length decreases by 1 until de.
If len(elements) == 0: # Add result when leaf node (Exception handling)
results.append( prev_elements[:] )
for e in elements:
print(f'e: {e}')
# All elements are delivered to the next spot for delivery on the next tour.
next_elements = elements[:]
next_elements.remove(e)
prev_elements.append(e)
dfs(next_elements)
# When looking at the position of the dash line of the output result, it is output after elements=[].
# -> Until then, you can see that dfs is recursively called.
print('- ' * 15)
prev_elements.pop()
print(f'poped prev_elements: {prev_elements}')
print('>' * 50)
dfs(nums)
return results
nums = [1, 2, 3]
_solver_obj = Solution()
results = _solver_obj.permute(nums)
print(results)
If you perform the above permutation code, it will be printed as follows. (If you don't understand, I'm sorry that I tend to print it out one by one.)
# elements: [1, 2, 3] # prev_elements: []
e: 1
# # elements: [2, 3] # prev_elements: [1]
e: 2
# # elements: [3] # prev_elements: [1, 2]
e: 3
# # elements: [] # prev_elements: [1, 2, 3]
- - - - - - - - - - - - - - -
poped prev_elements: [1, 2]
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
- - - - - - - - - - - - - - -
poped prev_elements: [1]
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
e: 3
# # elements: [2] # prev_elements: [1, 3]
e: 2
# # elements: [] # prev_elements: [1, 3, 2]
- - - - - - - - - - - - - - -
poped prev_elements: [1, 3]
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
- - - - - - - - - - - - - - -
poped prev_elements: [1]
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
- - - - - - - - - - - - - - -
poped prev_elements: []
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
e: 2
# # elements: [1, 3] # prev_elements: [2]
e: 1
# # elements: [3] # prev_elements: [2, 1]
e: 3
# # elements: [] # prev_elements: [2, 1, 3]
- - - - - - - - - - - - - - -
poped prev_elements: [2, 1]
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
- - - - - - - - - - - - - - -
poped prev_elements: [2]
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
e: 3
# # elements: [1] # prev_elements: [2, 3]
e: 1
# # elements: [] # prev_elements: [2, 3, 1]
- - - - - - - - - - - - - - -
poped prev_elements: [2, 3]
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
- - - - - - - - - - - - - - -
poped prev_elements: [2]
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
- - - - - - - - - - - - - - -
poped prev_elements: []
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
e: 3
# # elements: [1, 2] # prev_elements: [3]
e: 1
# # elements: [2] # prev_elements: [3, 1]
e: 2
# # elements: [] # prev_elements: [3, 1, 2]
- - - - - - - - - - - - - - -
poped prev_elements: [3, 1]
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
- - - - - - - - - - - - - - -
poped prev_elements: [3]
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
e: 2
# # elements: [1] # prev_elements: [3, 2]
e: 1
# # elements: [] # prev_elements: [3, 2, 1]
- - - - - - - - - - - - - - -
poped prev_elements: [3, 2]
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
- - - - - - - - - - - - - - -
poped prev_elements: [3]
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
- - - - - - - - - - - - - - -
poped prev_elements: []
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
The part that I don't understand is the part where the dash line is output and the popped prev_elements are output. I don't understand why prev_elements.pop() is so many times. I wonder which code makes this happen. Thank you
python recursive
You can also try running vs code in debugging mode. I think it's best to run it in debugging mode and follow it.
If you want to see the log, it's better to see the depth of the recursive function together. I believe it will be helpful if you add a parameter called depth and log it and look at the results and think about it.
from typing import List
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
results, prev_elements = [], []
def dfs(elements, depth=0):
print(" "*depth + f" # elements: {elements} # prev_elements: {prev_elements}")
# Len(element) == 0 because the length of the next_element given by the dfs factor decreases by 1 until the length of the next_element becomes the leaf node.
If len(elements) == 0: # Add result when leaf node (Exception handling)
results.append(prev_elements[:])
for e in elements:
print(" "*depth + f"e: {e}")
# All elements are delivered to the next spot for delivery on the next tour.
next_elements = elements[:]
next_elements.remove(e)
prev_elements.append(e)
dfs(next_elements, depth+1)
# When looking at the position of the dash line of the output result, it is output after elements=[].
# -> Until then, you can see that dfs is recursively called.
print(" "*depth + "- " * 15)
prev_elements.pop()
print(" "*depth + f"poped prev_elements: {prev_elements}")
print(" "*depth + ">" * 50)
dfs(nums)
return results
nums = [1, 2, 3]
_solver_obj = Solution()
results = _solver_obj.permute(nums)
print(results)
© 2024 OneMinuteCode. All rights reserved.