时间戳

首页 > 解决方案 > Scheme中列表的非递减列表？

list - Scheme中列表的非递减列表？

问题描述

我们需要一个名为 的 Scheme 函数nondecreaselist，它接收一个数字列表并输出一个列表列表，这些列表总体上具有相同顺序的相同数字，但分组为非递减的列表。

例如，如果我们有 input (1 2 3 4 1 2 3 4 1 1 1 2 1 1 0 4 3 2 1)，输出应该是：

((1 2 3 4) (1 2 3 4) (1 1 1 2) (1 1) (0 4) (3) (2) (1))

你将如何实现这一点？我知道我们必须使用递归。到目前为止我的尝试：

(define (nondecreaselist s) 
  (cond ((null? s) '())
        ((cons (cons (car s)
                     ((if (and (not (null? (cadr s)))
                               (not (> (car s) (cadr s))))
                          ((cadr s))
                          ('()))))
               (nondecreaselist (cdr s))))))

但是，这给了我错误：

(int) 不可调用：

标签： listsortingrecursionschemepartitioning

解决方案

(define decrease-list
  (lambda (l)
    ((lambda (s) (s s l cons))
     (lambda (s l col)
       ;; limitcase1: ()
       (if (null? l)
           (col '() '())
           ;; limitcase2: (a1)
           (if (null? (cdr l))
               (col l '())
               (let ((a1 (car l)) (a2 (cadr l)))
                 ;; limitcase3: (a1 a2)
                 (if (null? (cddr l))
                     (if (>= a2 a1)
                         (col l '())
                         (col (list a1) (list (cdr l))))
                     ;; most usual case: (a1 a2 ...)
                     (s s (cdr l)
                        (lambda (g l*)
                          (if (>= a2 a1)
                              (col (cons a1 g) l*)
                              (col (list a1) (cons g l*)))))))))))))

1 ]=> (decrease-list '(1 2 3 4 1 2 3 4 1 1 1 2 1 1 0 4 3 2 1))
;Value: ((1 2 3 4) (1 2 3 4) (1 1 1 2) (1 1) (0 4) (3) (2) (1))

我没有评论它，如果您有问题可以提出，但我认为您也可以自己研究我现在为您编写的代码。

另请注意，可以考虑限制情况()并(a1)跳出循环并仅检查一次这些情况：

(define decrease-list
  (lambda (l)
    ;; limitcase1: ()
    (if (null? l)
        '()
        ;; limitcase2: (a1)
        (if (null? (cdr l))
            (list l)
            ((lambda (s) (s s l cons))
             (lambda (s l col)
               (let ((a1 (car l)) (a2 (cadr l)))
                 ;; limitcase3: (a1 a2)
                 (if (null? (cddr l))
                     (if (>= a2 a1)
                         (col l '())
                         (col (list a1) (list (cdr l))))
                     ;; most usual case: (a1 a2 ...)
                     (s s (cdr l)
                        (lambda (g l*)
                          (if (>= a2 a1)
                              (col (cons a1 g) l*)
                              (col (list a1) (cons g l*)))))))))))))

推荐阅读