将列表排序为子列表

Question

我正在尝试创建一个程序来对列表进行排序,然后将列表中的每个部分分组到单独的列表中,并将其输出到列表列表中.这是一个应该更清楚的检查:

> (sort-lists > '())
empty

> (sort-lists < '(1 2 3))
(list (list 1 2 3))

> (sort-lists >= '(2 2 2 2))
(list (list 2 2 2 2))

> (sort-lists < '(5 4 3 2 1))
(list (list 5) (list 4) (list 3) (list 2) (list 1))

> (sort-lists < '(1 2 3 4 2 3 4 5 6 1 2 9 8 7))
(list
 (list 1 2 3 4)
 (list 2 3 4 5 6)
 (list 1 2 9)
 (list 8)
 (list 7))

这就是我所拥有的:

(define (sort-lists rel? ls)
  (cond
    [(empty? ls) '()]
    [(rel? (first ls) (first (rest ls)))
     (list (cons (first ls) (sort-lists rel? (rest ls))))]
    [else (cons (first ls) (sort-lists rel? (rest (rest ls))))]))

我遇到了(第一个(休息))部分的问题,因为如果没有第一个休息那么它会给出一个错误,与其余的休息一样.

此外,这必须是单通函数,在ISL +中没有任何助手.任何帮助都会很棒.

有没有办法使用local将解决方案与递归子问题合并到ans变量,然后完成答案.因此,对于(sort-lists < '(1 2 3 4 2 3 4 5 6 1 2 9 8 7)),您将定义ANS运行的结果(sort-lists < '(2 3 4 2 3 4 5 6 1 2 9 8 7)),这是'((2 3 4) (2 3 4 5 6) (1 2 9) (8) (7)).

Answer 1

我不会真的叫这个排序这么多,因为一些类型的划分.您正在尝试收集已根据谓词排序的最长的连续元素序列.我知道你说你必须将这一切都捆绑到一个函数中,但是首先将它作为单独的函数编写,然后将它们合并为一个函数可能要容易得多.

在解决这个问题时,将其分解为子任务可能会有所帮助.首先,在最高级别,当列表进入时,有一些升序元素的初始前缀,然后是其后的元素.结果应该是第一个前缀的列表,然后是处理其余元素的结果.这给了我们这样的结构:

(define (slice predicate lst)
  (if (empty? lst)
      ;; If lst is empty, then there no contiguous 
      ;; subsequences within it, so we return '() 
      ;; immediately.
      '()
      ;; Otherwise, there are elements in lst, and we 
      ;; know that there is definitely a prefix and
      ;; a tail, although the tail may be empty. Then
      ;; the result is a list containing the prefix,
      ;; and whatever the sliced rest of the list is.
      (let* ((prefix/tail (ordered-prefix predicate lst))
             (prefix (first prefix/tail))
             (tail (second prefix/tail)))
        (list* prefix (slice predicate tail)))))

我希望该功能的逻辑相对清晰.唯一可能有点不寻常的是let*,它执行顺序绑定,list**,与**cons相同.还有一个我们尚未定义的函数ordered-prefix的引用.它的任务是返回两个值的列表; 第一个是列表的有序前缀,第二个是该前缀后的列表尾部.现在我们只需编写该函数:

(define (ordered-prefix predicate lst)
  (cond
    ;; If the list is empty, then there's no prefix,
    ;; and the tail is empty too.
    ((empty? lst)
     '(() ()))
    ;; If the list has only one element (its `rest` is
    ;; empty, then the prefix is just that element, and 
    ;; the tail is empty.
    ((empty? (rest lst))
     (list (list (first lst)) '()))
    ;; Otherwise, there are at least two elements, and the
    ;; list looks like (x y zs...).
    (else 
     (let ((x (first lst))
           (y (second lst))
           (zs (rest (rest lst))))
       (cond
         ;; If x is not less than y, then the prefix is (x),
         ;; and the tail is (y zs...).
         ((not (predicate x y))
          (list (list x) (list* y zs)))
         ;; If x is less than y, then x is in the prefix, and the 
         ;; rest of the prefix is the prefix of (y zs...).  
         (else 
          (let* ((prefix/tail (ordered-prefix predicate (list* y zs)))
                 (prefix (first prefix/tail))
                 (tail (second prefix/tail)))
            (list (list* x prefix) tail))))))))

现在,这足以使切片工作:

(slice < '())                ;=> ()
(slice < '(1 2 3 4 2 3 4 5)) ;=> ((1 2 3 4) (2 3 4 5))

但是,它不是一个功能.要实现它,您需要将ordered-prefix的定义添加到slice的定义中.您可以使用let来绑定其他函数中的函数,例如:

(define (repeat-reverse lst)
  (let ((repeat (lambda (x)
                  (list x x))))
    (repeat (reverse lst))))

(repeat-reverse '(1 2 3)) ;=> ((3 2 1) (3 2 1))

但是,这对于ordered-prefix不起作用,因为ordered-prefix是递归的; 它需要能够引用自己.你可以用letrec做到这一点,它允许函数引用自己.例如:

(define (repeat-n-reverse lst n)
  (letrec ((repeat-n (lambda (x n)
                       (if (= n 0) 
                           '()
                           (list* x (repeat-n x (- n 1)))))))
    (repeat-n (reverse lst) n)))

(repeat-n-reverse '(1 2 3) 3)     ;=> ((3 2 1) (3 2 1) (3 2 1))
(repeat-n-reverse '(x y) 2)       ;=> ((y x) (y x))
(repeat-n-reverse '(a b c d e) 0) ;=> ()

好的,现在我们已经准备好把它们放在一起了.(由于ordered-prefix现在在 slice中定义,它已经可以访问谓词,我们可以从参数列表中删除它,但仍然使用它.)

(define (slice predicate lst)
  (letrec ((ordered-prefix
            (lambda (lst)
              (cond
                ((empty? lst)
                 '(() ()))
                ((empty? (rest lst))
                 (list (list (first lst)) '()))
                (else 
                 (let ((x (first lst))
                       (y (second lst))
                       (zs (rest (rest lst))))
                   (cond
                     ((not (predicate x y))
                      (list (list x) (list* y zs)))
                     (else 
                      (let* ((prefix/tail (ordered-prefix (list* y zs)))
                             (prefix (first prefix/tail))
                             (tail (second prefix/tail)))
                        (list (list* x prefix) tail))))))))))
    (if (empty? lst)
        '()
        (let* ((prefix/tail (ordered-prefix lst))
               (prefix (first prefix/tail))
               (tail (second prefix/tail)))
          (list* prefix (slice predicate tail))))))

这也是相对有效的.它没有分配任何不必要的数据,除了我使用的地方(list*y zs)为了清楚起见,其中的值与(rest lst)相同.你可能应该改变它,但为了清楚起见,我想保留它.

唯一的性能考虑因素是这不是尾递归,因此您使用了更多的堆栈空间.要解决这个问题,您需要将递归转换为反向构建列表的表单,然后在返回时将其反转.这就是我在原版中所做的事情(您仍然可以查看编辑历史记录),但对于看起来像是学术练习而言可能有些过分.