如何在继续循环时将新值绑定到 Racket 中的变量
How to bind new value to a variable in Racket while continuing loop
我有一个二维数字列表，表示 table 的条目，例如：
'((0 2 3)
(4 0 0)
(7 0 9))
目标是以每行和每列 只有一个 标记 0 的方式标记零。所以在在这个例子中，标记的零将是 (col 1 row 1) (col 2 row 3) (col 3 row 2)。这是Hungarian Algorithm.
的一步
我试图在 Scheme 中编写这块伪代码，但在不重新启动循环的情况下修改我的变量时遇到了问题。我不知道如何更改变量并从该行继续。
for r in rows
first := true
for c in cols
if A(r, c) == 0
if first
A(r, c) is assigned
first := false
for rr in rows
if A(rr, c) == 0 and r != rr
A(rr, c) is crossed out
else
A(r, c) is crossed out
例如将false赋值给first，或者交叉/赋值A(r, c)。怎么做？
我曾尝试为每个循环使用命名 let，但我找不到另一种方法将新值绑定到变量而不重新启动 let 循环。
我对你正在尝试做的事情感到有点困惑，但我认为是这样的：给定一些矩阵 A，return 最大可能的集合 'assignments' (r, c)，其中，对于每个赋值 (r, c) A(r, c) = 0，并且每个 r 或 c 在集合中出现不超过一次。我将定义一组 'complete' 赋值是一组赋值，其中包括每行的赋值（显然，对于行数多于列数的任何矩阵，不存在这样的集合）。
如果这是正确的，那么这里有一种在 Racket 中不使用任何赋值的方法。
首先，这里有一个小模块，可以让您构建数值矩阵：毫无疑问，Racket 中包含一个更具工业强度的数值矩阵版本，但我已经有了这个，而且我很懒。矩阵表示为
的函数
- 当不带参数调用时 return 矩阵的维度；
- 当使用两个参数调用时 return 该索引处的元素；
- （当使用单个参数调用时，相当于 Common Lisp 的
row-major-aref，用于调试）。
注意矩阵是不可变的table。
(module matrix racket
;; mindless numerical matrices
(provide (contract-out
(make-matrix
(-> (listof (listof number?))
(case->
(-> (values natural-number/c natural-number/c))
(-> natural-number/c number?)
(-> natural-number/c natural-number/c number?))))))
(define (make-matrix rows)
(let* ([r (length rows)]
[c (if (> r 0)
(for/fold ([cl (length (first rows))])
([col (in-list (rest rows))])
(if (and cl (= cl (length col))) cl #f))
0)]
[s (* r c)])
(unless c
(error 'make-matrix "not rectangular"))
(let ([v (for*/vector ([row (in-list rows)]
[e (in-list row)])
e)])
(case-lambda
;; A matrix is a function which ...
[()
;; ... with no arguments returns its dimensions ...
(values r c)]
[(index)
;; ... with one argument does row-major-aref ...
(when (>= index s)
(error 'matrix "index out of range"))
(vector-ref v index)]
[(row col)
;; ... with two arguments does aref.
(when (or (>= row r) (>= col c))
(error 'matrix "indices out of range"))
(vector-ref v (+ (* row c) col))])))))
所以，好的，假设我们可以编写一个函数来计算分配。几乎所有困难的部分（你可能不需要）是，如果没有完整的赋值集（例如，如果矩阵的一行没有零）return它可以找到的最大集合。另一方面，对于具有许多可能的赋值集的矩阵，下面的函数只是 return 一个。
首先，我想要某种方式来表示 table 的作业：我需要能够询问作业是否已经在 table 中以及 [=55= 有多大] 是，并用一个新的任务扩展它，return 一组新的任务。如果这些操作中的大多数花费的时间近似于恒定时间，那很好，但它们不必这样做。我还希望能够将 table 个作业转换为 (row column) 个列表的列表，按行排序。
所以这是根据 Racket 的字典接口实现的：
(define empty-assignments '())
(define assignments-count dict-count)
(define assignments-has-col? dict-has-key?)
(define (extend-assignments a col row)
;; Return a new set of assignments which extends a by col and row
(when (assignments-has-col? a col)
(error 'extend-assignments "adding an existing assignment"))
(if (null? a)
(hasheqv col row)
(dict-set a col row)))
(define (assignments->list assignments)
(sort (dict-map assignments (λ (col row) (list row col)))
< #:key car))
最后，考虑到所有这些，这是一个计算分配的函数。这确实有一个大技巧，当循环遍历列（内循环）找到一个赋值时，它会调用带有新赋值的行循环并添加一个重新启动，这只是一个可以调用以重新启动的函数从该列和行搜索。
此函数要么计算出完整的赋值集，要么失败：如果没有完整集，它不会 return 'best' 集。
(define (assignify m)
;; compute a set of assignments for m, or return #f
(let-values ([(rows cols) (m)])
(let row-loop ([row 0]
[assignments empty-assignments]
[restarts '()])
(if (= row rows)
;; we've got to the end
(cond [(= (assignments-count assignments) rows)
;; found enough assignments, we're done
(assignments->list assignments)]
[(not (null? restarts))
;; not enough assignments, but there are things to try
((first restarts))]
[else
;; fail
#f])
;; this is not the end
(let col-loop ([col 0])
(cond [(= col cols)
;; out of columns, loop on the next row
(row-loop (+ row 1) assignments restarts)]
[(and (zero? (m row col))
(not (assignments-has-col? assignments col)))
;; found an assignment, loop on the next row with
;; the assignment, pushing a restart
(row-loop (+ row 1)
(extend-assignments assignments col row)
(cons (thunk (col-loop (+ col 1))) restarts))]
[else
;; loop on next column
(col-loop (+ col 1))]))))))
如果您还希望函数 return 最大可能的赋值集之一，如果没有完整的集合，那么该函数会变得更加复杂和难以理解：
(define (assignify m)
;; Compute one of the best assignments for a matrix m
;;
(let-values ([(rows cols) (m)])
(let row-loop ([row 0]
[assignments empty-assignments]
[best-assignments empty-assignments]
[restarts '()])
(if (= row rows)
;; we've got to the end
(cond [(= (assignments-count assignments) rows)
;; found enough assignments, we're done
(assignments->list assignments)]
[(not (null? restarts))
;; not enough assignments, but there are things to try
((first restarts)
(if (> (assignments-count assignments)
(assignments-count best-assignments))
assignments
best-assignments))]
[else
;; Return the best we have
(assignments->list
(if (> (assignments-count assignments)
(assignments-count best-assignments))
assignments
best-assignments))])
;; this is not the end
(let col-loop ([col 0]
[best best-assignments])
(cond [(= col cols)
;; out of columns, loop on the next row
(row-loop (+ row 1)
assignments best
restarts)]
[(and (zero? (m row col))
(not (assignments-has-col? assignments col)))
;; found an assignment, loop on the next row with
;; the assignment, pushing a restart
(let ([ia (extend-assignments assignments col row)]
[rss (cons (λ (ba)
(col-loop (+ col 1) ba))
restarts)])
(row-loop (+ row 1) ia
(if (> (assignments-count ia)
(assignments-count best))
ia
best)
rss))]
[else
;; loop on next column
(col-loop (+ col 1) best)]))))))
现在
> (define m1 (make-matrix '((0 2 3)
(4 0 0)
(7 0 7))))
> (define m2 (make-matrix '((0 2 3)
(4 0 0)
(7 7 7))))
> (assignify m1)
'((0 0) (1 2) (2 1))
> (assignify m2)
'((0 0) (1 1))
我有一个二维数字列表，表示 table 的条目，例如：
'((0 2 3)
(4 0 0)
(7 0 9))
目标是以每行和每列 只有一个 标记 0 的方式标记零。所以在在这个例子中，标记的零将是 (col 1 row 1) (col 2 row 3) (col 3 row 2)。这是Hungarian Algorithm.
我试图在 Scheme 中编写这块伪代码，但在不重新启动循环的情况下修改我的变量时遇到了问题。我不知道如何更改变量并从该行继续。
for r in rows
first := true
for c in cols
if A(r, c) == 0
if first
A(r, c) is assigned
first := false
for rr in rows
if A(rr, c) == 0 and r != rr
A(rr, c) is crossed out
else
A(r, c) is crossed out
例如将false赋值给first，或者交叉/赋值A(r, c)。怎么做？
我曾尝试为每个循环使用命名 let，但我找不到另一种方法将新值绑定到变量而不重新启动 let 循环。
我对你正在尝试做的事情感到有点困惑，但我认为是这样的：给定一些矩阵 A，return 最大可能的集合 'assignments' (r, c)，其中，对于每个赋值 (r, c) A(r, c) = 0，并且每个 r 或 c 在集合中出现不超过一次。我将定义一组 'complete' 赋值是一组赋值，其中包括每行的赋值（显然，对于行数多于列数的任何矩阵，不存在这样的集合）。
如果这是正确的，那么这里有一种在 Racket 中不使用任何赋值的方法。
首先，这里有一个小模块，可以让您构建数值矩阵：毫无疑问，Racket 中包含一个更具工业强度的数值矩阵版本，但我已经有了这个，而且我很懒。矩阵表示为
的函数- 当不带参数调用时 return 矩阵的维度；
- 当使用两个参数调用时 return 该索引处的元素；
- （当使用单个参数调用时，相当于 Common Lisp 的
row-major-aref，用于调试）。
注意矩阵是不可变的table。
(module matrix racket
;; mindless numerical matrices
(provide (contract-out
(make-matrix
(-> (listof (listof number?))
(case->
(-> (values natural-number/c natural-number/c))
(-> natural-number/c number?)
(-> natural-number/c natural-number/c number?))))))
(define (make-matrix rows)
(let* ([r (length rows)]
[c (if (> r 0)
(for/fold ([cl (length (first rows))])
([col (in-list (rest rows))])
(if (and cl (= cl (length col))) cl #f))
0)]
[s (* r c)])
(unless c
(error 'make-matrix "not rectangular"))
(let ([v (for*/vector ([row (in-list rows)]
[e (in-list row)])
e)])
(case-lambda
;; A matrix is a function which ...
[()
;; ... with no arguments returns its dimensions ...
(values r c)]
[(index)
;; ... with one argument does row-major-aref ...
(when (>= index s)
(error 'matrix "index out of range"))
(vector-ref v index)]
[(row col)
;; ... with two arguments does aref.
(when (or (>= row r) (>= col c))
(error 'matrix "indices out of range"))
(vector-ref v (+ (* row c) col))])))))
所以，好的，假设我们可以编写一个函数来计算分配。几乎所有困难的部分（你可能不需要）是，如果没有完整的赋值集（例如，如果矩阵的一行没有零）return它可以找到的最大集合。另一方面，对于具有许多可能的赋值集的矩阵，下面的函数只是 return 一个。
首先，我想要某种方式来表示 table 的作业：我需要能够询问作业是否已经在 table 中以及 [=55= 有多大] 是，并用一个新的任务扩展它，return 一组新的任务。如果这些操作中的大多数花费的时间近似于恒定时间，那很好，但它们不必这样做。我还希望能够将 table 个作业转换为 (row column) 个列表的列表，按行排序。
所以这是根据 Racket 的字典接口实现的：
(define empty-assignments '())
(define assignments-count dict-count)
(define assignments-has-col? dict-has-key?)
(define (extend-assignments a col row)
;; Return a new set of assignments which extends a by col and row
(when (assignments-has-col? a col)
(error 'extend-assignments "adding an existing assignment"))
(if (null? a)
(hasheqv col row)
(dict-set a col row)))
(define (assignments->list assignments)
(sort (dict-map assignments (λ (col row) (list row col)))
< #:key car))
最后，考虑到所有这些，这是一个计算分配的函数。这确实有一个大技巧，当循环遍历列（内循环）找到一个赋值时，它会调用带有新赋值的行循环并添加一个重新启动，这只是一个可以调用以重新启动的函数从该列和行搜索。
此函数要么计算出完整的赋值集，要么失败：如果没有完整集，它不会 return 'best' 集。
(define (assignify m)
;; compute a set of assignments for m, or return #f
(let-values ([(rows cols) (m)])
(let row-loop ([row 0]
[assignments empty-assignments]
[restarts '()])
(if (= row rows)
;; we've got to the end
(cond [(= (assignments-count assignments) rows)
;; found enough assignments, we're done
(assignments->list assignments)]
[(not (null? restarts))
;; not enough assignments, but there are things to try
((first restarts))]
[else
;; fail
#f])
;; this is not the end
(let col-loop ([col 0])
(cond [(= col cols)
;; out of columns, loop on the next row
(row-loop (+ row 1) assignments restarts)]
[(and (zero? (m row col))
(not (assignments-has-col? assignments col)))
;; found an assignment, loop on the next row with
;; the assignment, pushing a restart
(row-loop (+ row 1)
(extend-assignments assignments col row)
(cons (thunk (col-loop (+ col 1))) restarts))]
[else
;; loop on next column
(col-loop (+ col 1))]))))))
如果您还希望函数 return 最大可能的赋值集之一，如果没有完整的集合，那么该函数会变得更加复杂和难以理解：
(define (assignify m)
;; Compute one of the best assignments for a matrix m
;;
(let-values ([(rows cols) (m)])
(let row-loop ([row 0]
[assignments empty-assignments]
[best-assignments empty-assignments]
[restarts '()])
(if (= row rows)
;; we've got to the end
(cond [(= (assignments-count assignments) rows)
;; found enough assignments, we're done
(assignments->list assignments)]
[(not (null? restarts))
;; not enough assignments, but there are things to try
((first restarts)
(if (> (assignments-count assignments)
(assignments-count best-assignments))
assignments
best-assignments))]
[else
;; Return the best we have
(assignments->list
(if (> (assignments-count assignments)
(assignments-count best-assignments))
assignments
best-assignments))])
;; this is not the end
(let col-loop ([col 0]
[best best-assignments])
(cond [(= col cols)
;; out of columns, loop on the next row
(row-loop (+ row 1)
assignments best
restarts)]
[(and (zero? (m row col))
(not (assignments-has-col? assignments col)))
;; found an assignment, loop on the next row with
;; the assignment, pushing a restart
(let ([ia (extend-assignments assignments col row)]
[rss (cons (λ (ba)
(col-loop (+ col 1) ba))
restarts)])
(row-loop (+ row 1) ia
(if (> (assignments-count ia)
(assignments-count best))
ia
best)
rss))]
[else
;; loop on next column
(col-loop (+ col 1) best)]))))))
现在
> (define m1 (make-matrix '((0 2 3)
(4 0 0)
(7 0 7))))
> (define m2 (make-matrix '((0 2 3)
(4 0 0)
(7 7 7))))
> (assignify m1)
'((0 0) (1 2) (2 1))
> (assignify m2)
'((0 0) (1 1))