0

リストを組み合わせるのに問題はありませんが、昇順で並べ替えるのが苦労しています。

 (define (combineASC l1 l2)
   (cond 
     ((null? l1) l2)
     (#t (cons (car l1) (combineASC (cdr l1) l2)))
     (sort l2 #'<))) ; I found this part in an online source

これは私が得る出力です:

(combineASC '(2 4 6) '(1 4 5))

(2 4 6 1 4 5)

誰か私に提案はありますか？

4

3 に答える 3

4

したがって、それぞれが既に昇順でソートされている 2 つの入力リストを結合しています。昇順でも、それらを 1 つに「織り込み」たいと考えています。

そのためには、両方の head 要素 (各入力リストからそれぞれ) を取得して比較します。次に、そのリストから最小のものを取り出し、同じ関数を使用して、残っているものをさらに組み合わせます。

関連するソートはありません。結果のリストは、それを定義するプロセスのおかげで、すでにソートされています。

この操作は一般に「マージ」と呼ばれます。重複を保持します。同様に、2 つの順序付けられたリストを 1 つにマージする重複除去機能は、「結合」と呼ばれます。これは、これらの順序付けされた (降順でない、または厳密に昇順の) リストは、セットの表現と見なすことができるためです。

注意すべきもう 1 つの微妙な点は、2 つの head 要素が等しい場合にどうするかということです。重複を保存することは既に決定していますが、2 つのうちどちらを最初に取り出すのでしょうか?

通常は左側です。次に、そのような定義されmergeた操作がマージソートの一部として使用されると、ソートは安定します（もちろん、そのためにもパーティション分割を適切に定義する必要があります）。安定とは、要素の元の順序が保持されることを意味します。

たとえば、ソートが安定している場合、ペアの最初の要素でソートすると、 は as ではなく as として(3,1) (1,2) (3,3)ソートされることが保証されます。(1,2) (3,1) (3,3)(1,2) (3,3) (3,1)

したがって、コードのスケルトンに従って、次のようになります

;; combine two non-decreasing lists into one non-decreasing list,
;; preserving the duplicates
(define (combineNONDECR l1 l2)
   (cond 
     ((null? l1) l2)
     ((null? l2) l1)
     ((<= (car l1) (car l2))
      (cons (car l1) (combineNONDECR (cdr l1) l2)))
     (t
      (cons (car l2) (combineNONDECR l1 (cdr l2))))))

しかし、結果が非​​減少ではなく昇順であることが本当に必要な場合は、これを少し調整する必要があります-ケースを個別に作成し、個別に処理して、重複が忍び寄るのを防ぎます(それぞれの昇順リストに重複はありませんが、リストにはそれらの 2 つの間にいくつかの重複が含まれる場合があります)。=

于 2012-10-04T18:15:47.463 に答える
1

テール再帰のため:)

(define (merge-sorted . lists)
  (define (%merge-sorted head tails)
    (cond
     ((null? tails) head)
     ((null? (car tails))
      (%merge-sorted head (cdr tails)))
     (else (let ((sorted
                  (sort tails
                        (lambda (a b)
                          (<= (car a) (car b))))))
             (%merge-sorted (cons (caar sorted) head)
                            (cons (cdar sorted) (cdr sorted)))))))
  (reverse (%merge-sorted '() lists)))

(merge-sorted '(1 2 3) '(4 5 6 7 8 9) '(2 4 6) '(1 3 5 7))
  • それはよりよくスケーリングします:P

これはウィルが話していたことだと思います：

(define (merge-sorted . lists)
  (define (%swap-if-greater lists)
    (define (%do-swap head next built tails)
      (cond
       ((null? tails)
        (append (reverse built)
                (cond
                 ((null? next) (list head))
                 ((> (car head) (car next))
                    (list next head))
                 (else (list head next)))))
       ((> (car head) (car next))
        (%do-swap head (car tails)
                  (cons next built) (cdr tails)))
       (else (append (reverse built)
                     (list head) (list next) tails))))
    (%do-swap (car lists)
              (if (null? (cdr lists)) '() (cadr lists))
              '() (if (null? (cdr lists)) '() (cddr lists))))
  (define (%merge-sorted head tails)
    (cond
     ((null? tails) head)
     ((null? (car tails))
      (%merge-sorted head (cdr tails)))
     (else (let ((sorted (%swap-if-greater tails)))
             (%merge-sorted (cons (caar sorted) head)
                            (cons (cdar sorted)
                                  (cdr sorted)))))))
  (reverse
   (%merge-sorted
    '() (sort lists (lambda (a b) (<= (car a) (car b)))))))

特にスキーム...ブール値に関する興味深い立場を考えると、私はこれについてあまり熱心ではありません。

于 2012-10-05T00:43:12.020 に答える
0 
(defun merge (l1 l2)
 (if (not (and (eql nil l1) (eql l2 nil))
  (if (> (car l1) (car l2))
     (cons (car l1) (merge (cdr l1) l2))
    (cons (car l2) (merge (cdr l2) l1)))
  ;;;append the not-nil string to the rest.
  )

それはうまくいくはずです（コードを完成させる必要がありますが、アイデアは明らかです）

このコードは common-lisp にあることに注意してください。

テクニックの詳細については、マージソートを参照してください

于 2012-10-04T18:17:01.430 に答える