在闭包中更新大矩阵中的子矩阵

Question

如何通过在特定位置插入一个较小的子矩阵来更新以嵌套向量表示的大型矩阵。

(def submatrix [[1 1] [1 1]])
(def matrix [[0 0 0] [0 0 0] [0 0 0]])
(def pos [1 1])
(defn update-matrix
   "Returns new matrix with the submatrix inserted at the [x y] pos as
    the top left position of the submatrix."
   [matrix submatrix pos]
    ; implementation??
)

期望输出：(为可读性格式化)

[[0 0 0]
 [0 1 1]
 [0 1 1]]

我迄今取得的进展：

我可以更新向量中的子向量：

(def v [0 1 2 3 4 5 6])
(def subv ["x" "y" "z"])
(def pos 2)
(concat (take pos v) subv (drop (+ pos (count subv)) v)
; [0 1 "x" "y" "z" 5 6]

但我不知道该从哪里出发，也不知道什么是最地道的。

Answer 1

做得对

我们可以将所需的函数定义为

(defn update-submatrix [m sub-m [x y]]
  (replace-subvec
    m
    (map (fn [l r] (replace-subvec l r y)) (subvec m x) sub-m)
    x))

..。其中，(replace-subvec v s start)将索引start中的向量v元素替换为序列s的元素，只要s持续。例如,

(replace-subvec (vec (range 10)) (range 3) 5)
; [0 1 2 3 4 0 1 2 8 9]

一个清晰但缓慢的实现是

(defn replace-subvec [v s start]
  (vec (concat (subvec v 0 start) s (subvec v (+ start (count s))))))

..。举个例子，

(def submatrix [[1 1] [1 1]])
(def matrix [[0 0 0] [0 0 0] [0 0 0]])
(def pos [1 1])

(update-submatrix matrix submatrix pos)
; [[0 0 0] [0 1 1] [0 1 1]]

加速它

加速update-submatrix的关键是加快replace-subvec的速度。

我们可以通过两种方式做到这一点：

• 通过循环递增来运行修改后的元素，
• 在函数中使用瞬态集合。

这给了我们

(defn replace-subvec [v s start]
  (loop [v (transient v), s s, i start]
    (if (empty? s)
      (persistent! v)
      (recur (assoc! v i (first s)) (rest s) (inc i)))))

效果是一样的。

Answer 2

您可以通过一个更新坐标序列缩小，在每一步中，将一个项从子矩阵复制到较大矩阵中的适当位置：

user> (defn update-matrix [matrix submatrix [y x]]
        (reduce (fn [m [row col]]
                  (assoc-in m [(+ row y) (+ col x)] 
                            (get-in submatrix [row col])))
                matrix
                (for [y (range (count submatrix))
                      x (range (count (first submatrix)))]
                  [y x])))
#'user/update-matrix
user> (update-matrix [[0 0 0] [0 0 0] [0 0 0]] [[1 1] [1 1]] [1 1])
[[0 0 0] [0 1 1] [0 1 1]]

Answer 3

这是我的15分钟。朝它开枪：

(defn update-matrix
  "Returns new matrix with the submatrix inserted at the [x y] pos as
  the top left position of the submatrix."
  [matrix submatrix pos]
  (let [[x y] pos
        height (count submatrix)
        width (count (get submatrix 0))]
    (loop [i 0 m matrix]
      (if (< i height)
        (let [item (vec (concat (vec (drop-last width (get matrix x))) (get submatrix i)))]
          (recur (+ 1 i) (assoc m (+ i y) item)))
        m))))

如果不起作用就告诉我。