Mercurial > lbo > hg > juliaplay
view python/dp.py @ 10:27f59dd007ab
dp: some minor matrix problems
author | Lewin Bormann <lbo@spheniscida.de> |
---|---|
date | Sun, 19 Feb 2023 16:35:57 +0100 |
parents | 33a23228ef5c |
children | ffb42007e4de |
line wrap: on
line source
import numpy as np from functools import cache @cache def number_of_binary_trees(n): if n == 0: return 1 elif n == 1: return 1 else: N = 0 for i in range(0, n): N += number_of_binary_trees(i) * number_of_binary_trees(n-i-1) return N @cache def number_of_full_binary_trees(n): if n <= 1: return 1 elif n%2 == 0: return 0 else: N = 0 # Only odd numbers possible. for nleft in range(1, n, 2): nright = n-1-nleft N += number_of_full_binary_trees(nleft) * number_of_full_binary_trees(nright) return N @cache def circle_chords(n): if n <= 1: return 0 elif n == 2: return 1 else: N = 0 for i in range(0, n): for j in range(i+1, n): left = j - i - 1 right = n - 2 - left N += 1 + circle_chords(left) * circle_chords(right) return N def subset_sum(s, n, tot): if tot == 0: return True if n < 0 or tot < 0: return False incl = subset_sum(s, n-1, tot-s[n]) if incl: return True excl = subset_sum(s, n-1, tot) return excl def equal_partitions(s): S = sum(s) if len(s) == 0 or S % 2 == 1: return False return subset_sum(s, len(s)-1, S/2) def find_min_matrix_path(mat, i=0, j=0, mem=dict()): # Find min-cost path from (0,0) to mat.shape - (1,1) if (i+1, j+1) == mat.shape: return mat[i, j] if (i,j) in mem: return mem[i,j] if i < mat.shape[0]-1: via_right = find_min_matrix_path(mat, i+1, j, mem) else: via_right = 1e6 if j < mat.shape[1]-1: via_down = find_min_matrix_path(mat, i, j+1, mem) else: via_down = 1e6 if via_right < via_down: mem[i,j] = mat[i,j] + via_right return mem[i,j] else: mem[i,j] = mat[i,j] + via_down return mem[i,j] def count_matrix_paths_with_cost(mat, cost, i=0, j=0): # Dest. is implicitly bottom right corner # Base case: if (i+1,j+1) == mat.shape: return cost == mat[i,j], [[(i,j)]] if i < mat.shape[0]-1: via_right, rp = count_matrix_paths_with_cost(mat, cost - mat[i,j], i+1, j) else: via_right, rp = 0, [] if j < mat.shape[1]-1: via_down, dp = count_matrix_paths_with_cost(mat, cost - mat[i,j], i, j+1) else: via_down, dp = 0, [] paths = [] if via_down+via_right > 0: paths = [[(i,j)] + p for p in rp+dp] return (via_down + via_right, paths) def min_sum_partition(s, n, S1=0, S2=0): if n < 0: return S1, S2 s11, s21 = min_sum_partition(s, n-1, S1+s[n], S2) s12, s22 = min_sum_partition(s, n-1, S1, S2+s[n]) if abs(s11-s21) < abs(s12-s22): print(f"{s[n]} in S1") return s11, s21 else: print(f"{s[n]} in S2") return s12, s22 def rodcut(L, lengths, prices, mem=dict()): if L < min(lengths): mem[L] = ([], 0) return [], 0 if L in mem: return mem[L] best_l, best_p = [], 0 for (l, p) in zip(lengths, prices): if L < l: continue l_, p_ = rodcut(L-l, lengths, prices) if p + p_ > best_p: best_p = p+p_ best_l = [l] + l_ mem[L] = [best_l, best_p] return best_l, best_p @cache def island_death(N, nstep, i=0, j=0): if i < 0 or j < 0 or i >= N or j >= N: return 1 elif nstep <= 0: return 0 else: return 1/4 * ( island_death(N, nstep-1, i-1, j) + island_death(N, nstep-1, i+1, j) + island_death(N, nstep-1, i, j-1) + island_death(N, nstep-1, i, j+1)) def matrix_sum(mat): sums = np.zeros_like(mat) sums[0,0] = mat[0,0] for i in range(1, mat.shape[0]): sums[i, 0] = sums[i-1, 0] + mat[i, 0] for j in range(1, mat.shape[1]): sums[0, j] = sums[0, j-1] + mat[0, j] sums[i, j] = sums[i, j-1] + sums[i-1, j] + mat[i,j] - sums[i-1,j-1] return sums def quick_matrix_sum(summat, c1, c2): a, b = c1 c, d = c2 corner, up, right = 0, 0, 0 if a > 0 and b > 0: corner = summat[a-1, b-1] if b > 0: up = summat[c, b-1] if a > 0: right = summat[a-1, d] return summat[c,d] - up - right + corner def max_k_submatrix(mat, k): summat = matrix_sum(mat) bestcoord, bestsum = None, -np.Inf for x in range(0, mat.shape[0]-k+1): for y in range(0, mat.shape[1]-k+1): cand = quick_matrix_sum(summat, (x,y), (x+k-1,y+k-1)) if cand > bestsum: bestsum = cand bestcoord = (x, y) return bestcoord, bestsum