当 pivot 和列表作为输入时，如何将分区分配到 return 两个列表输出？

Question

我正在尝试在使用分区的方案中执行快速排序实现，该分区需要两个参数，一个主元和一个列表。

如果我运行:

=>(分区'3'(5 7 8 6 4 2 1))

我希望输出为：

=>;值：((2 1) (3 5 7 8 6 4))

我正在使用此代码：

(define (partition lt? lst)
 (if (null? lst)
     (values '() '())
     (let ((rest (cdr lst)))
       (if (lt? (car lst) (car rest))
           (let ((left (partition lt? rest)))
             (values (cons (car lst) (car left))
                     (cdr left)))
           (let ((right (partition lt? rest)))
             (values (car right)
                     (cons (car lst) (cdr right)))))))

它给出了以下错误： Output

Answer 1

您的分区定义需要一个过程 lt? 和一个列表，但您发送的是 3 作为过程。您也许应该有 3 个参数，lt?、pivot 和 lst？这是您的错误消息的来源。 Here is a more elaborate explanation 此类错误及其可能的来源。

代码中有更多错误。 partition returns 两个值，但是您的代码在调用自身时没有使用适当的步骤来接收更多值，例如。 let-values。某些代码似乎需要一个包含结果的列表，而不是两个结果。

您还应该从最简单的情况开始测试。我会先做这些：

(partition > 3 '())      ; ==> (), ()
(partition > 3 '(1))     ; ==> (), (1)
(partition < 3 '(1))     ; ==> (1), ()
(partition < 3 '(4))     ; ==> (), (4)
(partition < 3 '(1 4))   ; ==> (1), (4)
(partition < 3 '(1 2 4)) ; ==> (1 2), (4)
(partition < 3 '(1 3 4)) ; ==> (1), (3 4)

Answer 2

除了将数字作为预期为函数的参数传递的问题之外，您还有另一个大问题。您的 partition 函数 return 有两个值，但它是递归的，每次调用它时，您都不会捕获它们，因此很难实际构建分区列表。

这里有几种方法可以做到这一点。我建议的第一个是尾递归，这要归功于一个名为 let 的 并且实际上只使用 values 作为其最终的 return 值。另一个演示了标准 call-with-values 函数来捕获递归调用 return 的两个值。

还有一个测试工具演示了另一种捕获多个值的方法，SRFI-11 let-values, which tends to be way more friendly than call-with-values. There's also SRFI-8's receive 是此处未显示的另一种方法。

(define (partition lt? what lst) (let loop ((lst lst) (lt '()) (gte '())) (cond ((null? lst) (values (reverse lt) (reverse gte))) ((lt? (car lst) what) (loop (cdr lst) (cons (car lst) lt) gte)) (else (loop (cdr lst) lt (cons (car lst) gte)))))) (define (partition2 lt? what lst) (if (null? lst) (values '() '()) (call-with-values (lambda () (partition2 lt? what (cdr lst))) (lambda (lt gte) (if (lt? (car lst) what) (values (cons (car lst) lt) gte) (values lt (cons (car lst) gte))))))) ;;; Uses list= from SRFI-1 and let-values from SRFI-11 and format from SRFI-48 (define (test-partition op num lst expected-left expected-right) (let-values (((actual-left actual-right) (partition op num lst))) (format #t "(partition ~A ~S ~S) => ~S and ~S: " (if (eqv? op <) "<" ">") num lst actual-left actual-right) (if (or (not (list= = actual-left expected-left)) (not (list= = actual-right expected-right))) (format #t "FAIL. Expected ~S and ~S instead.~%" expected-left expected-right) (format #t "PASS~%")))) (test-partition > 3 '() '() '()) (test-partition > 3 '(1) '() '(1)) (test-partition < 3 '(1) '(1) '()) (test-partition < 3 '(4) '() '(4)) (test-partition < 3 '(1 4) '(1) '(4)) (test-partition < 3 '(1 2 4) '(1 2) '(4)) (test-partition < 3 '(1 3 4) '(1) '(3 4))

Answer 3

我为你写的

(define (partition lt? pivot lst)
  ((lambda (s) (s s lst list))
   (lambda (s l* c)
     (if (null? l*)
         (c '() '())
         (let ((x (car l*)))
           (s s (cdr l*)
              (lambda (a b)
                (if (lt? x pivot)
                    (c (cons x a) b)
                    (c a (cons x b))))))))))

这是一个测试

1 ]=> (partition < '3 '(5 7 8 6 4 2 1))
;Value: ((2 1) (5 7 8 6 4))

当 pivot 和列表作为输入时，如何将分区分配到 return 两个列表输出？

How do I get the partition to return two list output when pivot and the list are given as inputs?

sorting

scheme