按给定数字的升序从列表中查找两个元素

Question

我想编写一个函数来搜索给定数字介于两者之间的两个元素； (element1 < num < element2)，以及它们在列表中第一个元素的位置。

;; check x is between num-1 and num-2
(define (in-between? x num-1 num-2)
      (or (and (> num-1 x) (< num-2 x))
          (and (> num-2 x) (< num-1 x))))

;; the list elements values are always in ascending order
(define lst '(0 0 0 1 1 1 2 2 2 3 3 4 4 5 5 6 6 6 7))

(define num 4.5)
;; expected-output=> 4.5 lies between element 4 and 5 of lst
;; '(4 5 12) ;; 12 is the position of first-element

;; output is list of 2 elements and the position of first-element
(define (find-interval u lst)
  (let* ([x (for/list ([a (drop-right lst 1)]
                       [b (cdr lst)]
                       [i (in-naturals)])
              (when (in-between? u a b)
                (list a b i)))])
    (car (filter list? x)))) ; to remove all #<void>
;; => '(4 5 12)

我必须使用 (car (filter list? x)) 来消除 x 中的 #<void> 输出，结果 '(#<void> #<void> #<void> #<void> #<void> #<void> #<void> #<void> #<void> #<void> #<void> #<void> (4 5 12) #<void> #<void> #<void> #<void> #<void>)。

如何防止列表中的 #<void> 来自 x 中的 for/list？ find-interval 函数中似乎有不必要的较长步骤。欢迎和赞赏所有建议。

Answer 1

假设列表始终按升序排列，可以使用以迭代方式编译的简单尾递归来定义函数：

(define (find-interval el lst (pos 0))
  (cond ((null? lst) '())
        ((null? (cdr lst)) '())
        ((>= (car lst) el) '())
        ((< (car lst) el (cadr lst)) (list (car lst) (cadr lst) pos))
        (else (find-interval el (cdr lst) (+ 1 pos)))))

(find-interval 4.5 '(0 0 0 1 1 1 2 2 2 3 3 4 4 5 5 6 6 6 7))  ; => '(4 5 12)

Answer 2

这里可以使用命名 let 来测试列表：

(define (find-interval u lst)
  (let loop ((idx 1))
    (if (= idx (length lst))
        #f
        (begin (let ((a (list-ref lst (sub1 idx)))
                     (b (list-ref lst idx)))
                 (if (in-between? u a b)
                     (list a b (sub1 idx))
                     (loop (add1 idx))))))))

它returns #f 如果列表中没有出现这种情况。

以下版本将生成一个列表列表，指示满足条件的多个位置：

(define (find-interval u lst)
  (let loop ((idx 1)
             (ol '()))
    (if (= idx (length lst))
        (reverse ol)
        (begin (let ((a (list-ref lst (sub1 idx)))
                     (b (list-ref lst idx)))
                 (if (in-between? u a b)
                     (loop (add1 idx) (cons (list a b (sub1 idx)) ol))
                     (loop (add1 idx) ol)))))))

(find-interval 4.5 '(0 0 0 1 1 1 2 2 2 3 3 4 4 5 5 6 6 6 7 4 6))
; => '((4 5 12) (7 4 18) (4 6 19))

输入列表不需要在上述任一函数中按排序顺序排列项目。

按给定数字的升序从列表中查找两个元素

Finding two elements from list in ascending order of given number

scheme

for-loop

list

void

racket