Definition and application example of Python divide and conquer

This paper introduces the definition and application of Python divide-and-conquer method. To share for your reference, specific as follows:

The problems that divide and conquer can solve generally have the following characteristics:

The problem can be easily solved by reducing it to a certain size
2) The problem can be decomposed into several similar problems of smaller scale, that is, the problem has optimal substructure property.
3) The solutions of the subproblems decomposed by the problem can be merged into the solutions of the problem;
4) Each sub-problem decomposed by this problem is independent of each other, that is, there are no common sub-problems among sub-problems.

The first feature is that most problems can be satisfied, because the computational complexity of the problem generally increases with the increase of the problem size.

The second feature is the premise of divide-and-conquer and it satisfies most problems, and it reflects the application of recursion;

The third feature is the key. The use of divide and conquer depends entirely on whether the problem has the third feature. If the first and second feature is present and the third feature is not, then greedy method or dynamic programming method can be considered.

The fourth feature relates to the efficiency of divide-and-conquer. If each subproblem is not independent, divide-and-conquer will do a lot of unnecessary work and repeatedly solve common subproblems. Although divide-and-conquer can be used, dynamic programming is generally better.

Title 1. Given a sequence table, write a divide-and-conquer algorithm to find its maximum value.

#  Basic subalgorithm (subproblem size is less than or equal to  2  When) 
def get_max(max_list):
  return max(max_list) #  Be lazy here! 
#  Divide and conquer method   version 1
def solve(init_list):
  n = len(init_list)
  if n <= 2: #  If the problem is less than or equal to  2 , the final settlement 
    return get_max(init_list)
  #  Decompose (subproblem size is  2 And the last 1 A possible for  1 ) 
  temp_list=(init_list[i:i+2] for i in range(0, n, 2))
  #  Divide and conquer, merge 
  max_list = list(map(get_max, temp_list))
  #  Recursion (tree) 
  solve(max_list)
#  Divide and conquer method   version 2
def solve2(init_list):
  n = len(init_list)
  if n <= 2: #  If the problem is less than or equal to  2 To solve 
    return get_max(init_list)
  #  Decompose (subproblem size is  n/2 ) 
  left_list, right_list = init_list[:n//2], init_list[n//2:]
  #  Recursion (tree), divide and conquer 
  left_max, right_max = solve2(left_list), solve2(right_list)
  #  merge 
  return get_max([left_max, right_max])
if __name__ == "__main__":
  #  The test data 
  test_list = [12,2,23,45,67,3,2,4,45,63,24,23]
  #  For maximum 
  print(solve(test_list)) # 67
  print(solve2(test_list)) # 67

Title 2. Given a sequence table, determine if an element is in it.

#  Subproblem algorithm (subproblem size is  1 ) 
def is_in_list(init_list, el):
  return [False, True][init_list[0] == el]
#  Divide and conquer method 
def solve(init_list, el):
  n = len(init_list)
  if n == 1: #  If the size of the problem is equal to  1 , solve directly 
    return is_in_list(init_list, el)
  #  Decompose (subproblem size is  n/2 ) 
  left_list, right_list = init_list[:n//2], init_list[n//2:]
  #  Recursion (tree), divide and conquer, merge 
  res = solve(left_list, el) or solve(right_list, el)
  return res
if __name__ == "__main__":
  #  The test data 
  test_list = [12,2,23,45,67,3,2,4,45,63,24,23]
  #  To find the 
  print(solve2(test_list, 45)) # True
  print(solve2(test_list, 5)) # False

Problem 3. Find the element of k 1 in the sequence, and find the linear time

#  Partition (based on pivot  pivot ), note: non-local division 
def partition(seq):
  pi = seq[0]              #  Select principal component 
  lo = [x for x in seq[1:] if x <= pi] #  All the little elements 
  hi = [x for x in seq[1:] if x > pi]  #  All the big elements 
  return lo, pi, hi
#  Find the first  k  Small element 
def select(seq, k):
  #  decomposition 
  lo, pi, hi = partition(seq)
  m = len(lo)
  if m == k:
    return pi        #  Solve! 
  elif m < k:
    return select(hi, k-m-1) #  Recursion (tree), divide and conquer 
  else:
    return select(lo, k)   #  Recursion (tree), divide and conquer 
if __name__ == '__main__':
  seq = [3, 4, 1, 6, 3, 7, 9, 13, 93, 0, 100, 1, 2, 2, 3, 3, 2]
  print(select(seq, 3)) #2
  print(select(seq, 5)) #2

Title 4. Quicksort

#  Partition (based on pivot  pivot ), note: non-local division 
def partition(seq):
  pi = seq[0]              #  Select principal component 
  lo = [x for x in seq[1:] if x <= pi] #  All the little elements 
  hi = [x for x in seq[1:] if x > pi]  #  All the big elements 
  return lo, pi, hi
#  Quick sort 
def quicksort(seq):
  #  If the problem is less than or equal to 1 To solve 
  if len(seq) <= 1: return seq
  #  decomposition 
  lo, pi, hi = partition(seq)
  #  Recursion (tree), divide and conquer, merge 
  return quicksort(lo) + [pi] + quicksort(hi)
seq = [7, 5, 0, 6, 3, 4, 1, 9, 8, 2]
print(quicksort(seq)) #[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

Title 5. Merge sort (2 sorted)

#  Merge sort 
def mergesort(seq):
  #  Decomposition (based on midpoint) 
  mid = len(seq) // 2
  left_seq, right_seq = seq[:mid], seq[mid:]
  #  Recursion (tree), divide and conquer 
  if len(left_seq) > 1: left_seq = mergesort(left_seq)
  if len(right_seq) > 1: right_seq = mergesort(right_seq)
  #  merge 
  res = []
  while left_seq and right_seq:     #  As long as neither is empty 
    if left_seq[-1] >= right_seq[-1]: #  Both tail larger, pop out 
      res.append(left_seq.pop())
    else:
      res.append(right_seq.pop())
  res.reverse()             #  Reverse order 
  return (left_seq or right_seq) + res  #  And then we're going to add what's left over seq
seq = [7, 5, 0, 6, 3, 4, 1, 9, 8, 2]
print(mergesort(seq)) #[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

Title 6. The Tower of Hannot

#  Hanoi 
def move(n, a, buffer, c):
  if n == 1:
    print(a,"->",c)
    #return
  else:
    #  Recursion (linear) 
    move(n-1, a, c, buffer)
    move(1, a, buffer, c) #  Or: print(a,"->",c)
    move(n-1, buffer, a, c)
move(3, "a", "b", "c")

Question 7. Take the stairs

Suppose you're climbing the stairs and need n steps to get to the top. But you can only climb one or two steps at a time. How many different ways can you climb to the top of the building?

#  Climb the stairs 
def climb(n=7):
  if n <= 2:
    return n
  return climb(n-1) + climb(n-2) #  Equivalent to the Fibonacci sequence! 
print(climb(5)) # 8
print(climb(7)) # 21

Question 8. Find one pair of n points on a given plane, so that the distance of the pair of n points is the smallest of all the pairs. (Nearest point problem)

from math import sqrt
#  A brute force method 
def solve(points):
  n = len(points)
  min_d = float("inf") #  Minimum distance: infinite 
  min_ps = None    #  Point to recent 
  for i in range(n-1):
    for j in range(i+1, n):
      d = sqrt((points[i][0] - points[j][0])**2 + (points[i][1] - points[j][1])**2) #  Two distance 
      if d < min_d:
        min_d = d            #  Modify the minimum distance 
        min_ps = [points[i], points[j]] #  Save the nearest pair 
  return min_ps
#  Nearest point right (error!) 
def nearest_dot(seq):
  #  Note: seq Prior to x Coordinate ordering 
  n = len(seq)
  if n <= 2: return seq #  If the size of the problem is equal to  2 , solve directly 
  #  Decomposition (subproblem size) n/2 ) 
  left, right = seq[0:n//2], seq[n//2:]
  print(left, right)
  mid_x = (left[-1][0] + right[0][0])/2.0
  #  Recursion, divide and conquer 
  lmin = (left, nearest_dot(left))[len(left) > 2]  #  Nearest point pair on the left 
  rmin = (right, nearest_dot(right))[len(right) > 2] #  Closest pair on the right 
  #  merge 
  dis_l = (float("inf"), get_distance(lmin))[len(lmin) > 1]
  dis_r = (float("inf"), get_distance(rmin))[len(rmin) > 1]
  d = min(dis_l, dis_r)  #  Nearest point pair distance 
  #  Dealing with banded areas near midline (approximate brute force) 
  left = list(filter(lambda p:mid_x - p[0] <= d, left))  # The distance to the left of the center line <=d The point of 
  right = list(filter(lambda p:p[0] - mid_x <= d, right)) # The distance to the right of the median line <=d The point of 
  mid_min = []
  for p in left:
    for q in right:
      if abs(p[0]-q[0])<=d and abs(p[1]-q[1]) <= d:   # If the right-hand side is at theta p Some of the (d,2d) between 
        td = get_distance((p,q))
        if td <= d:
          mid_min = [p,q]  #  record p . q Point to 
          d = td      #  Modify the minimum distance 
  if mid_min:
    return mid_min
  elif dis_l>dis_r:
    return rmin
  else:
    return lmin
#  Two distance 
def get_distance(min):
  return sqrt((min[0][0]-min[1][0])**2 + (min[0][1]-min[1][1])**2)
def divide_conquer(seq):
  seq.sort(key=lambda x:x[0])
  res = nearest_dot(seq)
  return res
#  test 
seq=[(0,1),(3,2),(4,3),(5,1),(1,2),(2,1),(6,2),(7,2),(8,3),(4,5),(9,0),(6,4)]
print(solve(seq)) # [(6, 2), (7, 2)]
#print(divide_conquer(seq)) # [(6, 2), (7, 2)]

Question 9. How many possible combinations of values are found from the array seq and for s

'''
 o 1 An algorithm is: N Number. Use one of them M The sum of any combination is equal to 1 A known number X . It is concluded that the M What are the Numbers. 
 Such as: 
seq = [1, 2, 3, 4, 5, 6, 7, 8, 9]
s = 14 #  and 
 All possible combinations of Numbers are: 
5+9, 6+8
1+4+9, 1+5+8, 1+6+7, 2+3+9, 2+4+8, 2+5+7, 3+4+7, 3+5+6
1+2+5+6, 1+3+4+6, 1+2+4+7, 1+2+3+8, 2+3+4+5
 A total of 15 Kind of 
'''
#  version 1 (Pure count) 
def find(seq, s):
  n = len(seq)
  if n==1:
    return [0, 1][seq[0]==s]
  if seq[0]==s:
    return 1 + find(seq[1:], s)
  else:
    return find(seq[1:], s-seq[0]) + find(seq[1:], s)
#  test 
seq = [1, 2, 3, 4, 5, 6, 7, 8, 9]
s = 14 #  and 
print(find(seq, s)) # 15
seq = [11,23,6,31,8,9,15,20,24,14]
s = 40 #  and 
print(find(seq, s)) #8
#  version 2  (print) 
def find2(seq, s, tmp=''):
  if len(seq)==0:  #  Termination conditions 
    return
  if seq[0] == s:        #  find 1 Kind of, 
    print(tmp + str(seq[0])) #  print 
  find2(seq[1:], s, tmp)               #  Tail recursion  --- Do not contain  seq[0]  In the case 
  find2(seq[1:], s-seq[0], str(seq[0]) + '+' + tmp)  #  Tail recursion  --- containing  seq[0]  In the case 
#  test 
seq = [1, 2, 3, 4, 5, 6, 7, 8, 9]
s = 14 #  and 
find2(seq, s)
print()
seq = [11,23,6,31,8,9,15,20,24,14]
s = 40 #  and 
find2(seq, s)

For more information about Python, you can see the following topics: Python Data Structure and Algorithm Tutorial, Python Socket Programming Skills Summary, Python Function Use Skills Summary, Python String Manipulation Skills Summary, Python Introduction and Advanced Classic Tutorial and Python File and Directory Operation Skills Summary.

I hope this article has been helpful in Python programming.