1

有点帮助，伙计们。你如何根据某种模式对列表进行排序一个例子是对 R、W、B 的列表进行排序，其中 R 先出现，然后是 W，然后是 B。有点(sortf '(W R W B R W B B))像(R R W W W B B B)

非常感谢任何答案。

4

4 回答 4

3

这是荷兰国旗问题的功能版本。这是我的两分钱-使用复杂的sort程序：O(n log n)

(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)：

(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)::

(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)如果我们将输入表示为一个向量，则可以构建一个最优的单遍命令式解决方案，它允许按索引引用元素。事实上，这就是问题的原始表述是如何解决的：

(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)])))

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

(sortf (vector 'W 'R 'W 'B 'R 'W 'B 'B 'R))
=> '#(R R R W W W B B B)
于 2013-08-08T13:26:47.890 回答
2

这是一个不使用sort或更高阶函数的解决方案。（即一点也不好玩）这并不是真正的排序，但它在不使用排序的情况下解决了您的问题。named let并且case是这个解决方案中最奇特的形式。

除非要求不使用排序，否则我不会这样做。我认为lepple 的回答既优雅又易于理解。

这个解决方案O(n)可能比其他有大量球的解决方案更快。

#!r6rs
(import (rnrs base))

(define (sort-flag lst)
  ;; count iterates over lst and counts Rs, Ws, and Bs
  (let count ((lst lst) (rs 0) (ws 0) (bs 0))
    (if (null? lst)
        ;; When counting is done build makes a list of
        ;; Rs, Ws, and Bs using the frequency of the elements
        ;; The building is done in reverse making the loop a tail call
        (let build ((symbols '(B W R))
                    (cnts (list bs ws rs))
                    (tail '()))
          (if (null? symbols)
              tail ;; result is done
              (let ((element (car symbols)))
                (let build-element ((cnt (car cnts))
                                    (tail tail))
                  (if (= cnt 0)
                      (build (cdr symbols)
                             (cdr cnts)
                             tail)
                      (build-element (- cnt 1) 
                                     (cons element tail)))))))
        (case (car lst)
          ((R) (count (cdr lst) (+ 1 rs) ws bs)) 
          ((W) (count (cdr lst) rs (+ 1 ws) bs)) 
          ((B) (count (cdr lst) rs ws (+ 1 bs)))))))
于 2013-08-08T15:05:55.290 回答
1

您只需使用内置排序或您已有的排序并使用自定义谓词。

(define (follow-order lst)
 (lambda (x y)
  (let loop ((inner lst))
  (cond ((null? inner) #f) 
        ((equal? x (car inner)) #t)
        ((equal? y (car inner)) #f)
        (else (loop (cdr inner)))))))

（排序'（WRWBRWB）（跟随'（RWB）））

; 值 50: (rrwwwbb)

于 2013-08-08T12:56:20.107 回答
1

进行查找，例如

(define sort-lookup '((R . 1)(W . 2)(B . 3)))

(define (sort-proc a b)
  (< (cdr (assq a sort-lookup))
     (cdr (assq b sort-lookup))))

(list-sort sort-proc '(W R W B R W B B))

可运行的 R6RS (IronScheme) 解决方案在这里：http ://eval.ironscheme.net/?id=110

于 2013-08-08T11:54:01.873 回答