按照模式排序 [英] Sorting in scheme following a pattern

问题描述

小伙伴们.你如何根据某种模式对列表进行排序一个例子是对 R、W、B 的列表进行排序，其中 R 首先出现，然后是 W，然后是 B.类似于 (sortf '(W R W B R W B B)) 到 (R R W W W B B B)

A little help, guys. How do you sort a list according to a certain pattern An example would be sorting a list of R,W,B where R comes first then W then B. Something like (sortf '(W R W B R W B B)) to (R R W W W B B B)

非常感谢任何答案.

推荐答案

这是 Dutch 的功能版本国旗问题.这是我的两分钱 - 使用具有 O(n log n) 复杂度的 sort 过程:

This is a functional version of the Dutch national flag problem. Here are my two cents - using the sort procedure with O(n log n) complexity:

(define sortf
  (let ((map '#hash((R . 0) (W . 1) (B . 2))))
    (lambda (lst)
      (sort lst
            (lambda (x y) (<= (hash-ref map x) (hash-ref map y)))))))

使用 filter 和 O(4n) 复杂度:

Using filter with O(4n) complexity:

(define (sortf lst)
  (append (filter (lambda (x) (eq? x 'R)) lst)
          (filter (lambda (x) (eq? x 'W)) lst)
          (filter (lambda (x) (eq? x 'B)) lst)))

使用 partition 和 O(3n) 复杂度::

Using partition with O(3n) complexity::

(define (sortf lst)
  (let-values (((reds others)
                (partition (lambda (x) (eq? x 'R)) lst)))
    (let-values (((whites blues)
                  (partition (lambda (x) (eq? x 'W)) others)))
      (append reds whites blues))))

以上解决方案以函数式编程风格编写，创建了一个包含答案的新列表.如果我们将输入表示为向量，则可以构建最佳的 O(n) 单遍命令式解决方案，该向量允许通过索引引用元素.事实上，这就是问题的原始表述是如何解决的:

The above solutions are written in a functional programming style, creating a new list with the answer. An optimal O(n), single-pass imperative solution can be constructed if we represent the input as a vector, which allows referencing elements by index. In fact, this is how the original formulation of the problem was intended to be solved:

(define (swap! vec i j)
  (let ((tmp (vector-ref vec i)))
    (vector-set! vec i (vector-ref vec j))
    (vector-set! vec j tmp)))

(define (sortf vec)
  (let loop ([i 0]
             [p 0]
             [k (sub1 (vector-length vec))])
    (cond [(> i k) vec]
          [(eq? (vector-ref vec i) 'R)
           (swap! vec i p)
           (loop (add1 i) (add1 p) k)]
          [(eq? (vector-ref vec i) 'B)
           (swap! vec i k)
           (loop i p (sub1 k))]
          [else (loop (add1 i) p k)])))

请注意，先前的解决方案会就地改变输入向量.它非常优雅，并且按预期工作:

Be aware that the previous solution mutates the input vector in-place. It's quite elegant, and works as expected:

(sortf (vector 'W 'R 'W 'B 'R 'W 'B 'B 'R))
=> '#(R R R W W W B B B)

这篇关于按照模式排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！