Python Partitioning Method Definition and Application Examples in Detail

# Basic subalgorithms (for subproblem sizes less than or equal to 2)
def get_max(max_list):
  return max(max_list) # Here's a steal!
# Partition law Version 1
def solve(init_list):
  n = len(init_list)
  if n <= 2: # If the size of the problem is less than or equal to 2, finalize the solution
    return get_max(init_list)
  # Decomposition (subproblem size 2, last possible 1)
  temp_list=(init_list[i:i+2] for i in range(0, n, 2))
  # Partition, merger
  max_list = list(map(get_max, temp_list))
  # Recursion (tree)
  solve(max_list)
# Partitioning Version II
def solve2(init_list):
  n = len(init_list)
  if n <= 2: # If the problem size is less than or equal to 2, solve the
    return get_max(init_list)
  # Decomposition (subproblem size n/2)
  left_list, right_list = init_list[:n//2], init_list[n//2:]
  # Recursion (tree), partitioning
  left_max, right_max = solve2(left_list), solve2(right_list)
  # Merge
  return get_max([left_max, right_max])
if __name__ == "__main__":
  # Test data
  test_list = [12,2,23,45,67,3,2,4,45,63,24,23]
  # Find the maximum value
  print(solve(test_list)) # 67
  print(solve2(test_list)) # 67

# Algorithm for subproblems (subproblem size 1)
def is_in_list(init_list, el):
  return [False, True][init_list[0] == el]
# Partitioning
def solve(init_list, el):
  n = len(init_list)
  if n == 1: # If the problem size is equal to 1, solve it directly
    return is_in_list(init_list, el)
  # Decomposition (subproblem size n/2)
  left_list, right_list = init_list[:n//2], init_list[n//2:]
  # Recursion (trees), partitioning, merging
  res = solve(left_list, el) or solve(right_list, el)
  return res
if __name__ == "__main__":
  # Test data
  test_list = [12,2,23,45,67,3,2,4,45,63,24,23]
  # Find
  print(solve2(test_list, 45)) # True
  print(solve2(test_list, 5)) # False

# Delineation (based on master pivot), note: not in situ
def partition(seq):
  pi = seq[0]              # Pick the main element
  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 kth smallest element
def select(seq, k):
  # Decompose
  lo, pi, hi = partition(seq)
  m = len(lo)
  if m == k:
    return pi        # Settle!
  elif m < k:
    return select(hi, k-m-1) # Recursion (tree), partitioning
  else:
    return select(lo, k)   # Recursion (tree), partitioning
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

# Delineation (based on master pivot), note: not in situ
def partition(seq):
  pi = seq[0]              # Pick the main element
  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
# Rapid sort
def quicksort(seq):
  # If the problem size is less than or equal to 1, solve the
  if len(seq) <= 1: return seq
  # Decompose
  lo, pi, hi = partition(seq)
  # Recursion (trees), partitioning, merging
  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]

# Merge sort
def mergesort(seq):
  # Decomposition (based on midpoint)
  mid = len(seq) // 2
  left_seq, right_seq = seq[:mid], seq[mid:]
  # Recursion (tree), partitioning
  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]: # The larger of the two tails, eject
      (left_seq.pop())
    else:
      (right_seq.pop())
  ()             # Reverse order
  return (left_seq or right_seq) + res  # Preceded by the remaining non-empty 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]

# Hannover Tower
def move(n, a, buffer, c):
  if n == 1:
    print(a,"->",c)
    #return
  else:
    # Recursive (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")

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

from math import sqrt
# Brute force method
def solve(points):
  n = len(points)
  min_d = float("inf") # Minimum distance: infinity
  min_ps = None    # Nearest point to
  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) # Distance between two points
      if d < min_d:
        min_d = d            # Modify the minimum distance
        min_ps = [points[i], points[j]] # Save the closest point pairs
  return min_ps
# Closest point to point (error reported!)
def nearest_dot(seq):
  # Note: seq is pre-ordered for the x-coordinate
  n = len(seq)
  if n <= 2: return seq # If the problem size is equal to 2, solve it 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, partitioning
  lmin = (left, nearest_dot(left))[len(left) > 2]  # Left nearest point pair
  rmin = (right, nearest_dot(right))[len(right) > 2] # Nearest point 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-to-point distance
  # Treating the band near the center line (near brute force)
  left = list(filter(lambda p:mid_x - p[0] <= d, left))  # Points to the left of the median line at a distance <=d
  right = list(filter(lambda p:p[0] - mid_x <= d, right)) # Points to the right of the median line at a distance <=d
  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 partial point is between (d,2d) of p points
        td = get_distance((p,q))
        if td <= d:
          mid_min = [p,q]  # Record p, q point pairs
          d = td      # Modify the minimum distance
  if mid_min:
    return mid_min
  elif dis_l>dis_r:
    return rmin
  else:
    return lmin
# Distance between two points
def get_distance(min):
  return sqrt((min[0][0]-min[1][0])**2 + (min[0][1]-min[1][1])**2)
def divide_conquer(seq):
  (key=lambda x:x[0])
  res = nearest_dot(seq)
  return res
# Testing
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)]

'''
Find an algorithm: n numbers, add any combination of M of them to equal a known number X. Derive which numbers these M numbers are.
For example:
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
Total 15 kinds
'''
# 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)
# Testing
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:        # If one is found, then
    print(tmp + str(seq[0])) # Print
  find2(seq[1:], s, tmp)               # Tail recursion --- without seq[0]
  find2(seq[1:], s-seq[0], str(seq[0]) + '+' + tmp)  # Tail recursion - case containing seq[0]
# Testing
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)