4

Lisp の宿題があり、苦労しています。

ユニオン操作を実行する関数を作成する必要があります。この関数は、アトムまたはリストのいずれかの形式で 2 つの入力を取り、すべての要素を結合して、順序を維持し、括弧のすべてのレベルを取り除きます。

関数の出力:

(my-union 'a 'b)                         ;; (a b)
(my-union 'a '(b))                       ;; (a b)
(my-union '(a b) '(b c))                 ;; (a b c)
(my-union '(((a))) '(b(c((d e))a)))      ;; (a b c d e)

私はLispにかなり慣れていません。これは私がこれまでに書いたもので、3番目の例でのみ機能します:

(defun new-union (a b)
 (if (not b)
      a
      (if (member (car b) a)
        (new-union a (cdr b))
        (new-union (append a (list (car b))) (cdr b)))))

どんな助けでも大歓迎です！

4

3 に答える 3

5

これはあなたの最初の宿題で、Lisp は初めてなので、パフォーマンスを気にせず、CL が提供するツールをうまく利用する、非常に単純なトップダウン アプローチを次に示します。

Common Lisp には、既に重複を削除する関数があります: remove-duplicates. キーワード引数と一緒に使用すると、:from-end「順序が保持されます」。flattenここで、任意にネストされたリストを平坦化する関数があると想像してください。次に、あなたの質問に対する解決策は次のようになります。

(defun new-union (list1 list2)
  (remove-duplicates (flatten (list list1 list2)) :from-end t))

これは、それ以上の制限が与えられておらず、パフォーマンスについてあまり心配する本当の理由がない場合に問題にアプローチする方法です。現在のツールボックスを可能な限り使用し、必要がない限り車輪を再発明しないでください。

このように問題に取り組むと、要するにflatten関数を書くことになりますが、これは演習として残しておきます。それほど難しいことではありません。簡単なオプションの 1 つは、再帰関数を記述して、次のように問題にアプローチすることです。

平坦化されるリストの最初の要素自体がリストである場合、平坦化された最初の要素を平坦化された残りに追加します。最初の要素がリストでない場合は、フラット化されたリストの残りの部分に追加します。入力がまったくリストでない場合は、それを返します。

これは良い練習になるはずで、ほんの数行のコードで実行できます。

(非常に正確にしたい場合は、ヘルパー関数を使用して作業を行い、ラッピング関数で引数が本当にリストであるかどうかを確認してください。それ以外の場合は、flattenアトムでも機能しますが、これは問題になる場合とそうでない場合があります。 .)

今、あなたが書いたと仮定しますflatten：

> (defun new-union (list1 list2)
    (remove-duplicates (flatten (list list1 list2)) :from-end t))
NEW-UNION
> (new-union 'a 'b)
(A B)
> (new-union 'a '(b))
(A B)
> (new-union '(a b) '(b c))
(A B C)
> (new-union '(((a))) '(b (c ((d e)) a)))
(A B C D E)
于 2012-09-30T13:10:32.393 に答える
3

これにアプローチする 1 つの方法は、懸念事項を分離することです。1つは平坦化です。もう 1 つは重複の削除です。もう 1 つは結果の構築です。

結果として空のリストから始めて、最初のリストの要素を追加し、結果に既に含まれている要素をスキップします。

次に、2 番目のリストの要素で同じことを行い、それらを同じ結果リストに追加します。

(defun my-union (a b &aux (res (list 1)) (p res))
  (nadd-elts p a)
  (nadd-elts p b)
  (cdr res))

nadd-eltspリストの最後に追加し、たとえば を使用して最後のセル ( が指す) を破壊的に更新しrplacdます。例はこちらです。

要素を追加するには、フラット化nadd-elts手順をエミュレートし、重複をチェックした後に各リーフ要素を追加します。pres

破壊的な更新を行わずに機能的なスタイルで作業する場合、一般的なアプローチは同じままです。空の結果リストから始めて、最初のリストをそれに追加します-重複なしで-次に2番目。

(defun my-union (a b &aux res)
  (setq res (add-into res a))
  (setq res (add-into res b))
  res)

あとはadd-into関数の実装です。

(defun add-into (res a &aux r1 r2)
  (cond
     ((atom a) .... )
     (T (setq r1 (add-into res (car a)))
        (setq r2 (............ (cdr a)))
        r2)))

set上記は、補助変数やプリミティブなしで書き直すことができます。方法を見つけてみてください... OK、これが私が意味したことです:

(defun my-union (a b) (add-into NIL (cons a b)))

(defun add-into (res a)
  (cond
     ((atom a) .... )
     (T (add-into (add-into res (car a)) 
                  (cdr a)))))
于 2012-09-30T07:57:22.887 に答える
2

ハッシュ テーブルの使用が許可されていない場合を除き (何らかの理由で以前にこれを要件として遭遇したことがあります)、結果のセットを作成するのに役立つ順序付け関数を考え出すことができます。検索を何度も繰り返すことです。

また、ネストされたリストが許可されているため、問題はツリー内の重複を削除するだけに縮小されます (処理を開始する前に、必要な数のリストを単純に追加できるため)。

ここで、それを行う方法の例をいくつか示します。

;; Large difference between best and worst case.
;; Lists containing all the same items will be processed
;; in square time
(defun union-naive (list &rest lists)
  (when lists (setf list (append list lists)))
  (let (result)
    (labels ((%union-naive (tree)
               (if (consp tree)
                   (progn
                     (%union-naive (car tree))
                     (when (cdr tree) (%union-naive (cdr tree))))
                   (unless (member tree result)
                     (setq result (cons tree result))))))
      (%union-naive list) result)))

;; Perhaps the best solution, it is practically linear time
(defun union-hash (list &rest lists)
  (when lists (setf list (append list lists)))
  (let ((hash (make-hash-table)) result)
    (labels ((%union-hash (tree)
               (if (consp tree)
                   (progn
                     (%union-hash (car tree))
                     (when (cdr tree) (%union-hash (cdr tree))))
                   (setf (gethash tree hash) t))))
      (%union-hash list))
    (maphash
     #'(lambda (a b)
         (declare (ignore b))
         (push a result)) hash)
    result))

;; This will do the job in more time, then the
;; solution with the hash-map, but it requires
;; significantly less memory. Memory is, in fact
;; a more precious resource some times, but you
;; have to decide what algo to use based on the
;; data size
(defun union-flatten (list &rest lists)
  (when lists (setf list (append list lists)))
  (labels ((%flatten (tree)
             (if (consp tree)
                 (if (cdr tree)
                     (nconc (%flatten (car tree))
                            (%flatten (cdr tree)))
                     (%flatten (car tree)))
                 (list tree))))
    ;; the code below is trying to do something
    ;; that you could've done using 
    ;; (remove-duplicates (%flatten list))
    ;; however sorting and then removing duplicates
    ;; may prove to be more efficient
    (reduce
     #'(lambda (a b)
         (cond
           ((atom a) (list a))
           ((eql (car a) b) b)
           (t (cons b a))))
     (sort (%flatten list)
           #'(lambda (a b)
               (string< (symbol-name a)
                        (symbol-name b)))))))



(union-naive '(((a))) '(b(c((d e))a)))
(union-hash '(((a))) '(b(c((d e))a)))
(union-flatten '(((a))) '(b(c((d e))a)))

要素の順序付けに使用した関数は普遍的ではないことに注意してください。ただし、あらゆる種類のデータに対して代替関数を思いつくことができるでしょう。一般に、高速ハッシュ関数はどれでもかまいませんが、簡単にするためにこれを使用しました。

于 2012-09-30T12:25:35.760 に答える