On recursion: Figuring out how to call an identical self, how to “enter” and how to “return”
- Hanoi
- Eight queen
- Quick sort
Hanoi
def hanoi(n, src='a', buf='b', dst='c'):
N plates, moved from SRC, cached with BUF, to DST """
if n == 1:
print(f'{src}->{dst}', end='\t')
else:
hanoi(n- 1, src, dst, buf)
hanoi(1, src, buf, dst)
hanoi(n- 1, buf, src, dst)
hanoi(4)
Copy the codea->b a->c b->c a->b c->a c->b a->b a->c b->c b->a c->a b->c a->b a->c b->c
Copy the codeEight queen
Backtracking method is used to solve the N queen problem
def is_valid(alist, i_row, v_column):
for i in range(i_row): I_row = 0; i_row = 0 Range (i_row -1), i_row-1
if alist[i] == v_column or abs(i_row-i) == abs(alist[i]-v_column):
return False
return True
def n_queen(n, alist, row=0):
Backtracking method to solve n queen problem: Place queen in row 1 on the alist[row] column (1 queen per row)
if row == n - 1:
The correct output must be here
for col in range(n):
if is_valid(alist, row, col):
alist[row] = col
print(alist) It is possible to use yield instead of print to produce a sequence of results, but since this is a row= n-1 call, yield does not yield at the row=0 level
return False
else:
# The backtracking part is here
for col in range(n):
if is_valid(alist, row, col):
alist[row] = col
n_queen(n, alist, row+1)
# if it reaches this point, the call in the previous sentence is returned, and the next loop should be performed
return False
def solve_nqueen(n):
alist = [- 99.]*n
n_queen(n, alist)
solve_nqueen(8)
Copy the codeIn short, backtracking is like going through a maze. Make a mark when you see a fork in the road, then try each fork, and if you don’t get there, return to the last mark.
What if you want to save the final result to some data structure?
The most straightforward idea is to change print to yield.
In recursion, the yield is returned only on the last row, and this yield can only be seen by its caller, n_queen, on the next-to-last row of the recursive stack.
How to do? I’m going to yield from each recursion.
Change to yield implementation
def is_valid(alist, i_row, v_column):
for i in range(i_row): I_row = 0; i_row = 0 Range (i_row -1), i_row-1
if alist[i] == v_column or abs(i_row-i) == abs(alist[i]-v_column):
return False
return True
def n_queen(n, alist, row=0):
Backtracking method to solve n queen problem: Place queen in row 1 on the alist[row] column (1 queen per row)
if row == n - 1:
The correct output must be here
for col in range(n):
if is_valid(alist, row, col):
alist[row] = col
yield tuple(alist) It is possible to use yield instead of print to produce a sequence of results, but since this is a row= n-1 call, yield does not yield at the row=0 level
# here, can't yield alist.
# yield alist means to throw alist (address), so you end up with a series (92) of identical lists (addresses).
The solve_nqueen function uses list(
) to generate a list of results so that each element of the list is at the same address.
Since the scope of Alist is the entire recursive stack, elements in Alist will be modified in subsequent program execution.
# So, the end result will be the last attempt repeated 92 times.
[:] alist. Copy () create a copy of the list object.
return
else:
# The backtracking part is here
for col in range(n):
if is_valid(alist, row, col):
alist[row] = col
yield from n_queen(n, alist, row+1)
# if it reaches this point, the call in the previous sentence is returned, and the next loop should be performed
return
def solve_nqueen(n):
alist = [- 99.]*n
res = tuple(n_queen(n, alist))
print(len(res))
print(res)
if __name__ == '__main__':
solve_nqueen(8)
Copy the code92
((0, 4, 7, 5, 2, 6, 1, 3), (0, 5, 7, 2, 6, 3, 1, 4), (0, 6, 3, 5, 7, 1, 4, 2), (0, 6, 4, 7, 1, 3, 5, 2), (1, 3, 5, 7, 2, 0, 6, 4), (1, 4, 6, 0, 2, 7, 5, 3), (1, 4, 6, 3, 0, 7, 5, 2), (1, 5, 0, 6, 3, 7, 2, 4), (1, 5, 7, 2, 0, 3, 6, 4), (1, 6, 2, 5, 7, 4, 0, 3), (1, 6, 4, 7, 0, 3, 5, 2), (1, 7, 5, 0, 2, 4, 6, 3), (2, 0, 6, 4, 7, 1, 3, 5), (2, 4, 1, 7, 0, 6, 3, 5), (2, 4, 1, 7, 5, 3, 6, 0), (2, 4, 6, 0, 3, 1, 7, 5), (2, 4, 7, 3, 0, 6, 1, 5), (2, 5, 1, 4, 7, 0, 6, 3), (2, 5, 1, 6, 0, 3, 7, 4), (2, 5, 1, 6, 4, 0, 7, 3), (2, 5, 3, 0, 7, 4, 6, 1), (2, 5, 3, 1, 7, 4, 6, 0), (2, 5, 7, 0, 3, 6, 4, 1), (2, 5, 7, 0, 4, 6, 1, 3), (2, 5, 7, 1, 3, 0, 6, 4), (2, 6, 1, 7, 4, 0, 3, 5), (2, 6, 1, 7, 5, 3, 0, 4), (2, 7, 3, 6, 0, 5, 1, 4), (3, 0, 4, 7, 1, 6, 2, 5), (3, 0, 4, 7, 5, 2, 6, 1), (3, 1, 4, 7, 5, 0, 2, 6), (3, 1, 6, 2, 5, 7, 0, 4), (3, 1, 6, 2, 5, 7, 4, 0), (3, 1, 6, 4, 0, 7, 5, 2), (3, 1, 7, 4, 6, 0, 2, 5), (3, 1, 7, 5, 0, 2, 4, 6), (3, 5, 0, 4, 1, 7, 2, 6), (3, 5, 7, 1, 6, 0, 2, 4), (3, 5, 7, 2, 0, 6, 4, 1), (3, 6, 0, 7, 4, 1, 5, 2), (3, 6, 2, 7, 1, 4, 0, 5), (3, 6, 4, 1, 5, 0, 2, 7), (3, 6, 4, 2, 0, 5, 7, 1), (3, 7, 0, 2, 5, 1, 6, 4), (3, 7, 0, 4, 6, 1, 5, 2), (3, 7, 4, 2, 0, 6, 1, 5), (4, 0, 3, 5, 7, 1, 6, 2), (4, 0, 7, 3, 1, 6, 2, 5), (4, 0, 7, 5, 2, 6, 1, 3), (4, 1, 3, 5, 7, 2, 0, 6), (4, 1, 3, 6, 2, 7, 5, 0), (4, 1, 5, 0, 6, 3, 7, 2), (4, 1, 7, 0, 3, 6, 2, 5), (4, 2, 0, 5, 7, 1, 3, 6), (4, 2, 0, 6, 1, 7, 5, 3), (4, 2, 7, 3, 6, 0, 5, 1), (4, 6, 0, 2, 7, 5, 3, 1), (4, 6, 0, 3, 1, 7, 5, 2), (4, 6, 1, 3, 7, 0, 2, 5), (4, 6, 1, 5, 2, 0, 3, 7), (4, 6, 1, 5, 2, 0, 7, 3), (4, 6, 3, 0, 2, 7, 5, 1), (4, 7, 3, 0, 2, 5, 1, 6), (4, 7, 3, 0, 6, 1, 5, 2), (5, 0, 4, 1, 7, 2, 6, 3), (5, 1, 6, 0, 2, 4, 7, 3), (5, 1, 6, 0, 3, 7, 4, 2), (5, 2, 0, 6, 4, 7, 1, 3), (5, 2, 0, 7, 3, 1, 6, 4), (5, 2, 0, 7, 4, 1, 3, 6), (5, 2, 4, 6, 0, 3, 1, 7), (5, 2, 4, 7, 0, 3, 1, 6), (5, 2, 6, 1, 3, 7, 0, 4), (5, 2, 6, 1, 7, 4, 0, 3), (5, 2, 6, 3, 0, 7, 1, 4), (5, 3, 0, 4, 7, 1, 6, 2), (5, 3, 1, 7, 4, 6, 0, 2), (5, 3, 6, 0, 2, 4, 1, 7), (5, 3, 6, 0, 7, 1, 4, 2), (5, 7, 1, 3, 0, 6, 4, 2), (6, 0, 2, 7, 5, 3, 1, 4), (6, 1, 3, 0, 7, 4, 2, 5), (6, 1, 5, 2, 0, 3, 7, 4), (6, 2, 0, 5, 7, 4, 1, 3), (6, 2, 7, 1, 4, 0, 5, 3), (6, 3, 1, 4, 7, 0, 2, 5), (6, 3, 1, 7, 5, 0, 2, 4), (6, 4, 2, 0, 5, 7, 1, 3), (7, 1, 3, 0, 6, 4, 2, 5), (7, 1, 4, 2, 0, 6, 3, 5), (7, 2, 0, 5, 1, 4, 6, 3), (7, 3, 0, 2, 5, 1, 6, 4))
Copy the codeSomeone else’s code
import random
In the definition of state, state is used to mark the position of each queen, where the index is used to represent the vertical coordinate and the corresponding value of the base is the horizontal coordinate. For example, state[0]=3 indicates that the queen is located in the fourth column of the first row
def conflict(state, nextX):
nextY = len(state)
for i in range(nextY):
# If the position of the next queen is adjacent to the position of the current queen, or on the same diagonal, then there is a conflict and needs to be rearranged
if abs(state[i]-nextX) in (0, nextY-i):
return True
return False
# Use a generator to generate the position of each queen and recursively achieve the position of the next queen.
def queens(num, state=(a)):
for pos in range(num):
if not conflict(state, pos):
# Generate position information for the current queen
if len(state) == num- 1:
yield (pos, )
Otherwise, add the current queen's position information to the status list and pass it to the next queen.
else:
for result in queens(num, state+(pos,)):
yield (pos, ) + result
# To visualize the board, use X to represent the position of each queen
def prettyprint(solution):
def line(pos, length=len(solution)):
return '. ' * (pos) + 'X ' + '. '*(length-pos- 1)
for pos in solution:
print(line(pos))
if __name__ == "__main__":
prettyprint(random.choice(list(queens(8))))
# print(list(queens(8)))
Copy the code. . . . X . . .
. . X . . . . .
X . . . . . . .
. . . . . X . .
. . . . . . . X
. X . . . . . .
. . . X . . . .
. . . . . . X .
Copy the codeQuick sort
53 27 88 31 95 47
27 88 31 95 47 - 53
|
47 27 88 31 95 - 53
|
47 27 31 95 88 - 53
|
47 27 31 95 88 - 53
||
47 27 31 53 95 88
-----------------------------
47 27 31
27 31 - 47
|
31 27 - 47
||
31 27 47
--------
31 27
27 31
-------------------
95 88
88 95
Copy the codeThe general idea of this algorithm is as follows:
- So let’s take the left-most element and call it pivot.
- I’m going to start at the right and I’m going to pick a value that’s smaller than pivot and I’m going to put it on the left.
- The assignment
- The pointer on the right moves one bit to the left
- I’m going to start at the far left and I’m going to pick something larger than pivot and I’m going to put it on the far right.
- The assignment
- Move the left pointer one bit to the right
- Finally, you get the position of the pivot, and the left and right lists split by pivot. Do the same for each list until there are enough elements in the list
import random
def partition(alist, left, right):
pivot = alist[left]
while left < right:
while left < right and alist[right] >= pivot:
right -= 1
if left < right:
alist[left] = alist[right]
left += 1
while left < right and alist[left] <= pivot:
left += 1
if left < right:
alist[right] = alist[left]
right -= 1
pivot_loc = left
return pivot_loc
def quick_sort(alist, left=0, right=None):
if right == None:
right = len(alist) - 1
if left >= right:
# Here, only two elements need to be considered. After pivot_LOc is obtained, it will either be 0 or 1.
Pivot_loc +1 or -1, left=0, right=1, so left>=right,
# You don't have to do anything.
return
pivot_loc = partition(alist, left, right)
quick_sort(alist, left, pivot_loc - 1)
quick_sort(alist, pivot_loc + 1, right)
if __name__ == '__main__':
alist = [random.randrange(0.1000) for _ in range(100)]
quick_sort(alist)
print(alist)
Copy the code[10, 32, 23, 23, 117, 65, 65, 99, 99, 135, 118, 118, 118, 283, 183, 189, 204, 204, 212, 212, 244, 261, 189, 277, 283, 285, 303, 301, 303, 318, 308, 318, 308, 305, 305, 373, 373, 377, 556, 423, 423, 509, 483, 488, 504, 488, 521, 509, 535, 535, 533, 618, 609, 618, 649, 626, 712, 658, 686, 686, 691, 721, 721, 732, 749, 623, 623, 781, 784, 784, 781, 798, 809, 810, 798, 817, 822, 822, 836, 836, 904, 858, 858, 888, 888, 898, 900, 900, 869, 900, 917, 917, 903, 952, 957, 979, 979]Copy the code