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

これは、オランダ国旗問題の機能版です。これが私の2セントです-複雑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は、このソリューションで最もエキゾチックな形式です。

ソートを使用しないことが必要でない限り、私はこのようにはしませんでした。レプルの答えはエレガントでわかりやすいと思います。

このソリューションは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 に答える