问题

I have translated the code portion for you:

我正在尝试编写一个Scheme函数，使用高斯消元法来计算给定矩阵（以列表列表的形式表示）的秩。

在代码中，我将解释我尝试做的事情，并希望有人告诉我哪里出错了，或者如何纠正它。

在“iter-rows”函数中，我遍历行并对每行执行高斯消元，以将矩阵转换为行梯阵形式：

* `below-pivot`将在给定行的枢轴下执行消元步骤。

* `factor-rec`在这里，我计算在消元过程中需要将一行乘以的因子。

* `elimination`函数在枢轴下方的其余行上执行消元操作。

* 至于`update-matrix`函数，它将从另一行中减去一行的多个。

* 最后，计算所有非零行以找到秩。

由于列表是不可变的，我在每次调用时传递它们的值。

以下是代码供参考：

Scheme
#lang racket

(define (rank matrix)
(define (iter-rows index rows-len matrix)
(if (= index rows-len)
matrix
(let ((pivot (list-ref (list-ref matrix index) index)))
(if (= pivot 0)
(iter-rows (+ index 1) rows-len matrix)
(begin
(below-pivot (+ index 1) rows-len matrix pivot index)
(iter-rows (+ index 1) rows-len matrix))))))

(define (below-pivot from-index rows-len matrix pivot i)
(if (= from-index rows-len)
matrix
(begin
(factor-rec (+ from-index 1) rows-len matrix i pivot)
(below-pivot (+ from-index 1) rows-len matrix pivot i)))))

(define (factor-rec j rows-len matrix i pivot)
(if (= j rows-len)
matrix
(begin
(let ([factor (/ (list-ref (list-ref matrix j) i) pivot)])
(elimination i i rows-len matrix j factor)))))

(define (elimination k i rows-len matrix j factor)
(if (= k rows-len)
matrix
(begin
(update-matrix matrix j k i factor)
(elimination (+ k 1) i rows-len matrix j factor)))))

(define (update-matrix matrix j k i factor)
(let ((new-cdr (- (list-ref (list-ref matrix j) k)
(* factor (list-ref (list-ref matrix i) k)))))

  (list (list-ref matrix i)
        (cons new-cdr (list-tail (list-ref matrix j) k))))))

(let ((rows-len (length matrix)))
(iter-rows 0 rows-len matrix))

(define (count-nonzero-rows matrix)
(let loop ((matrix matrix) (rank- 0))
(cond
((null? matrix) rank-)
((not (all-zeroes? (car matrix)))
(loop (cdr matrix) (+ rank- 1)))
(else (loop (cdr matrix) rank-)))))

(let* ((rank (count-nonzero-rows matrix)))
rank))

(define (all-zeroes? row)
(for/and ([x row]) (= x 0))))

如果需要进一步解释或有其他问题，请随时提出。

<details>
<summary>英文:</summary>

I am trying to write a function in Scheme which will calculate the rank of a given matrix (in the form of a list of lists) using Gaussian Elimination method.

I&#39;ll explain what I am trying to do in the code and would appreciate if anyone could tell me what I did wrong \ how to correct it.

In `iter-rows` function, I iterate over the rows and perform Gaussian Elimination on each row to make the matrix into row echelon form:

* `below-pivot` will basically perform the elimination step below the pivot in the given row.

* `factor-rec` here I calculate the factor needed to multiply a row during the elimination process.

* `elimination` function performs the elimination itself over the rest of the rows below the pivot.

* As for the `update-matrix` function, it will subtract a multiple of one row from another.

* Finally, count all non-zero rows to find the rank.

Since lists are immutable I am passing their value with every call.

Here&#39;s the code for reference:
```Scheme
#lang racket

(define (rank matrix)
  (define (iter-rows index rows-len matrix)
    (if (= index rows-len)
        matrix
          (let ((pivot (list-ref (list-ref matrix index) index)))
            (if (= pivot 0)
                (iter-rows (+ index 1) rows-len matrix)
                (begin
                  (below-pivot (+ index 1) rows-len matrix pivot index)
                  (iter-rows (+ index 1) rows-len matrix))))))

  (define (below-pivot from-index rows-len matrix pivot i)
    (if (= from-index rows-len)
        matrix
        (begin
          (factor-rec (+ from-index 1) rows-len matrix i pivot)
          (below-pivot (+ from-index 1) rows-len matrix pivot i))))

  (define (factor-rec j rows-len matrix i pivot)
    (if (= j rows-len)
        matrix
        (begin
          (let ([factor (/ (list-ref (list-ref matrix j) i) pivot)])
            (elimination i i rows-len matrix j factor)))))

  (define (elimination k i rows-len matrix j factor)
    (if (= k rows-len)
        matrix
        (begin
          (update-matrix matrix j k i factor)
          (elimination (+ k 1) i rows-len matrix j factor))))

  (define (update-matrix matrix j k i factor)
    (let ((new-cdr (- (list-ref (list-ref matrix j) k)
                      (* factor (list-ref (list-ref matrix i) k)))))
      (list (list-ref matrix i)
            (cons new-cdr (list-tail (list-ref matrix j) k)))))

  (let ((rows-len (length matrix)))
    (iter-rows 0 rows-len matrix))

  (define (count-nonzero-rows matrix)
    (let loop ((matrix matrix) (rank- 0))
      (cond 
          ((null? matrix) rank-)
          ((not (all-zeroes? (car matrix))) 
           (loop (cdr matrix) (+ rank- 1)))
          (else (loop (cdr matrix) rank-)))))

  (let* ((rank (count-nonzero-rows matrix)))
    rank))

(define (all-zeroes? row)
  (for/and ([x row]) (= x 0)))

I'm new to Scheme so would appreciate any other tips as well.

Thanks.

答案1

得分: 3

Here is the translation of the code you provided:

;lang racket

(define (extract matrix i j)
  (vector-ref (vector-ref matrix i) j))

(define (swap-rows! matrix i j)
  (let ((tmp (vector-ref matrix i)))
    (vector-set! matrix i (vector-ref matrix j))
    (vector-set! matrix j tmp)))

(define (scale-row! matrix i factor)
  (define (vector-scale vec factor)
    (vector-map (curry * factor) vec))
  (let* ((row (vector-ref matrix i))
         (scaled-row (vector-scale row factor)))
    (vector-set! matrix i scaled-row)))

(define (eliminate-rows! matrix i j pivot)
  (define (eliminate-row! matrix i j pivot)
    (when (< i (vector-length matrix))
      (let* ((element-i-j (extract matrix i j))
             (factor (/ element-i-j pivot)))
        (scale-row! matrix i factor)
        (eliminate-row! matrix (add1 i) j pivot)))))
  (eliminate-row! matrix (add1 i) j pivot))

(define (gaussian-rank matrix (i 0) (j 0) (rank 0))
  (cond ((>= i (vector-length matrix)) rank)
        ((zero? (extract matrix i j)) (gaussian-rank matrix (add1 i) j rank))
        (else
          (swap-rows! matrix i rank)
          (let ((pivot (extract matrix rank j)))
            (when (not (zero? pivot))
              (scale-row! matrix rank (/ 1 pivot))
              (eliminate-rows! matrix rank j pivot))
            (gaussian-rank matrix (add1 i) (add1 j) (add1 rank))))))

(define mat (vector #(1 2 3) #(0 1 2) #(0 0 1)))
(gaussian-rank mat) ;=> 1

你提供的代码已经被翻译成中文。如果您有任何其他问题或需要进一步的帮助，请随时告诉我。

#lang racket

(define (extract matrix i j)
  (vector-ref (vector-ref matrix i) j))
  
(define (swap-rows! matrix i j)
  (let ((tmp (vector-ref matrix i)))
    (vector-set! matrix i (vector-ref matrix j))
    (vector-set! matrix j tmp)))

(define (scale-row! matrix i factor)
  (define (vector-scale vec factor)
    (vector-map (curry * factor) vec))
  (let* ((row (vector-ref matrix i))
         (scaled-row (vector-scale row factor)))
    (vector-set! matrix i scaled-row)))

(define (eliminate-rows! matrix i j pivot)
  (define (eliminate-row! matrix i j pivot)
    (when (< i (vector-length matrix))
      (let* ((element-i-j (extract matrix i j))
             (factor (/ element-i-j pivot)))
        (scale-row! matrix i factor)
        (eliminate-row! matrix (add1 i) j pivot))))
  (eliminate-row! matrix (add1 i) j pivot))

(define (gaussian-rank matrix (i 0) (j 0) (rank 0))
  (cond ((>= i (vector-length matrix)) rank)
        ((zero? (extract matrix i j)) (gaussian-rank matrix (add1 i) j rank))
        (else
          (swap-rows! matrix i rank)
          (let ((pivot (extract matrix rank j)))
            (when (not (zero? pivot))
              (scale-row! matrix rank (/ 1 pivot))
              (eliminate-rows! matrix rank j pivot))
            (gaussian-rank matrix (add1 i) (add1 j) (add1 rank))))))

(define mat (vector #(1 2 3) #(0 1 2) #(0 0 1)))
(gaussian-rank mat) ;;=> 1

(define (get-row matrix i)
  (vector-ref matrix i))

(define (get-element matrix i j)
  (vector-ref (vector-ref matrix i) j))

(define (swap-rows! matrix i j)
  (let ((tmp (vector-ref matrix i)))
    (vector-set! matrix i (vector-ref matrix j))
    (vector-set! matrix j tmp)))

(define-syntax while
  (syntax-rules () ((_ pred b1 ...) (let loop () (when pred b1 ... (loop))))))

(define (gaussian-rank matrix)
  (let* ((nrows (vector-length matrix))
         (ncols (if (zero? nrows) 0 (vector-length (vector-ref matrix 0))))
         (rank 0))
    (for ([ncol (in-range ncols)])
      (let ([pivot-row rank])
        (while (and (< pivot-row nrows)
                     (zero? (get-element matrix pivot-row ncol)))
            (set! pivot-row (add1 pivot-row)))
        (unless (= pivot-row nrows)
          (swap-rows! matrix pivot-row rank)
          (let ([pivot-value (get-element matrix rank ncol)])
            (for ([nrow (in-range (add1 rank) nrows)])
              (let* ([factor (/ (get-element matrix nrow ncol) pivot-value)]
                     [scaled-diffed-row (vector-map (lambda (x y) (- x (* factor y)))
                                      (get-row matrix nrow)
                                      (get-row matrix rank))])
                (vector-set! matrix nrow scaled-diffed-row))))
          (set! rank (add1 rank)))))
     rank))

> (define mat (vector #(1 2 3) #(4 5 6) #(7 8 9)))
> (gaussian-rank mat)
2
> mat
'#(#(1 2 3) #(0 -3 -6) #(0 0 0))

        (while (and (< pivot-row nrows)
                     (zero? (get-element matrix pivot-row ncol)))
            (set! pivot-row (add1 pivot-row)))

`_`:    while
`pred`: (and (< pivot-row nrows)
                     (zero? (get-element matrix pivot-row ncol)))
`b1`:   (set! pivot-row (add1 pivot-row))
`...`:  in this case nothing

(let loop ()
  (when (and (< pivot-row nrows)
                     (zero? (get-element matrix pivot-row ncol)))
    (set! pivot-row (add1 pivot-row))
    (loop))

答案2

得分: 3

You have a recurrent problem with your functions. For instance,

(define (elimination k i rows-len matrix j factor)
  (if (= k rows-len)
      matrix
      (begin
        (update-matrix matrix j k i factor)
        (elimination (+ k 1) i rows-len matrix j factor))))

I assume update-matrix (inside the begin) is supposed to return an updated matrix. Yet the returned value is ignored, and the old value of matrix is used again, in the call to elimination.

You can fix this in a purely syntactical (i.e. mechanistic) manner by changing begin to let* in the above, as

(define (elimination k i rows-len matrix j factor)
  (if (= k rows-len)
      matrix
      (let* ([matrix (update-matrix matrix j k i factor)])  ; <<< here
        (elimination (+ k 1) i rows-len matrix j factor))))

After this is done for all functions with this problem, running e.g.

(rank '((1 2 3) (4 5 6) (7 8 9)))

produces the following error,

. . list-ref: index too large for list
  index: 2
  in: '((1 2 3) (0 7 8 9))

inside update-matrix. You will need to debug this further.

Another thing is, all these functions actually implement the same "folding" pattern, passing along an "accumulator" value, as it is being updated, from step to step.

You've coded it in an awkward manner though, passing around many of all those parameters without change. This style is used in languages without the concept of nested scope, like Prolog. But in Scheme, this is normally coded with an inner definition, or an equivalent letrec or named let construct.

And you're already using this construct in your count-nonzero-rows.

Following this pattern, the above function becomes

(define (elimination k i rows-len matrix j factor)
  (let loop ((k k)
             (matrix matrix))
    (if (= k rows-len)
       matrix
       (loop (+ k 1)
             (update-matrix matrix j k i factor)))))

 ;;   (let* ([matrix (update-matrix matrix j k i factor)]) 
 ;;     (elimination (+ k 1) i rows-len matrix j factor))))
 ;;                  ^^^^^^             ^^^^^^
 ;;                  only these two arguments are changing

But actually, this folding pattern is already available in Racket as for/fold, so you can just use that, similar to how you already use for/and in all-zeroes?.

  (define (elimination k i rows-len matrix j factor)
    (if (= k rows-len)
        matrix
        (begin
          (update-matrix matrix j k i factor)
          (elimination (+ k 1) i rows-len matrix j factor))))

  (define (elimination k i rows-len matrix j factor)
    (if (= k rows-len)
        matrix
        (let* ([matrix (update-matrix matrix j k i factor)])  ; <<< here
          (elimination (+ k 1) i rows-len matrix j factor))))

(rank '((1 2 3) (4 5 6) (7 8 9)))

. . list-ref: index too large for list
  index: 2
  in: '((1 2 3) (0 7 8 9))

  (define (elimination k i rows-len matrix j factor)
    (let loop ((k k)
               (matrix matrix))
      (if (= k rows-len)
         matrix
         (loop (+ k 1)
               (update-matrix matrix j k i factor)))))

   ;;   (let* ([matrix (update-matrix matrix j k i factor)]) 
   ;;     (elimination (+ k 1) i rows-len matrix j factor))))
   ;;                  ^^^^^^             ^^^^^^
   ;;                  only these two arguments are changing