循环在方案中对列表进行 n 次排队

Question

我正在尝试编写一个带有两个参数的函数，一个列表和循环次数 n。我一直在尝试实现一个 let 循环来调用辅助函数，将结果保存到一个变量，然后每次循环将 n 递减 1，然后在 n 达到 0 时停止，但我不确定该怎么做。 .

这是我的代码：

; helper function to queue it once
    (define (queue lst)
      (if (empty? lst)
          '()
      (append (cdr lst) (list (car lst)))))

;main function that calls helper function 
(define (queueLoop n lst)
 (if (empty? lst)
      '()
  (let loop ((res (queue lst))
             (lst (queue lst)))
    (cond
     [(> n 0)
      ((- n 1) (loop (queue res) (rest lst)))]
     (else
      (loop (queue res) (rest lst)))))))

Answer 1

请记住，在 Scheme 中，大多数操作不会改变变量，而是 return 修改后的新值。以此为例：

(- n 1)

上面那行不是修改n的值，它是return一个等于n减去的新值1，除非你将它存储在某处或将它作为参数传递给函数调用，否则该值将丢失（事实上，这就是正在发生的事情）。

更新： 现在您已经发布了示例 input/output，很清楚您打算做什么。这是使用内置过程编写解决方案的另一种简单方法，它可以处理极端情况：

(define (queueLoop n lst)
  (let ((x (min n (length lst))))
    (append (drop lst x)
            (take lst x))))

例如：

(queueLoop 1 '())
=> '()
(queueLoop 0 '(1 2 3 4))
=> '(1 2 3 4)
(queueLoop 3 '(1 2 3 4))
=> '(4 1 2 3)
(queueLoop 5 '(1 2 3 4))
=> '(1 2 3 4)

Answer 2

这是我会做的：

(define (rotate-left-inc lst n)
  (let-values ([(tail head) (split-at lst n)])
    (append head tail)))

至于你自己的卷，使用 cons 是 O(1) 和 append 是 O(n) 的事实我会这样做：

;; rotate once in O(n) time
(define (rotate-left-once lst)
  (append (cdr lst) (list (car lst))))

;; rotate n times in O(n) time
(define (rotate-left-on lst n)
  (let loop ([head lst] [rtail '()] [n n])
    (if (<= n 0)
        (append head (reverse rtail))
        (loop (cdr head) (cons (car head) rtail) (sub1 n)))))

虽然没有办法重复旋转一次并获得有效的过程：

;; rotate n times in O(n^2) time
(define (rotate-left lst n)
  (let loop ([n n] [lst lst])
    (if (<= n 0)
        lst
        (loop (sub1 n) (rotate-left-once lst)))))

使用原始版本时旋转的数字越长，这会变得非常慢，而使用 append 一次的版本要快得多：

(define lst1 (make-list 200 198))
(define lst2 (make-list 20000 19998))
(define lst3 (make-list 2000000 1999998))
(for-each (lambda (lst)
            (display (car lst))
            (newline)
            (display "O(n) inc")
            (time (rotate-left-inc lst (car lst)))
            (display "O(n) roll")
            (time (rotate-left-on lst (car lst)))
            (display "O(n^2)")
            (time (rotate-left lst (car lst))))
          (list lst1 lst2 lst3))

我电脑上的输出清楚地显示指数时间需要很多时间：

198
O(n) inccpu time: 1 real time: 0 gc time: 0
O(n) rollcpu time: 0 real time: 0 gc time: 0
O(n^2)cpu time: 0 real time: 1 gc time: 0
19998
O(n) inccpu time: 1 real time: 0 gc time: 0
O(n) rollcpu time: 0 real time: 1 gc time: 0
O(n^2)cpu time: 4846 real time: 4884 gc time: 1295
1999998
O(n) inccpu time: 207 real time: 209 gc time: 160
O(n) rollcpu time: 279 real time: 282 gc time: 234
O(n^2) (didn't wait for it. Gave up after 5 minutes)

循环在方案中对列表进行 n 次排队

Loop to queue a list n times in scheme

queue

scheme

racket