同等のクラスLisp

Question

同等のクラスのプログラムを作成し、この出力を取得する必要があります...

(equiv '((a b) (a c) (d e) (e f) (c g) (g h))) 
 => ((a b c g h) (d e f))

(equiv '((a b) (c d) (e f) (f g) (a e)))
 => ((a b e f g) (c d))

基本的に、セットは順序が重要ではないリストですが、要素は複数回表示されません。関数は、ペアのリスト（一部の同等の関係に応じて関連する要素）を受け入れ、反復または割り当てステートメントを使用せずに一連の等価クラスを返します（例： do, set!, 、など）。

ただし、などのユーティリティを設定します set-intersection, set-union リストと組み込み関数の重複を排除する関数 union, intersection, 、 と remove-duplicates 許可されています。

どうもありがとう！

ちなみに、それは宿題の質問ではありません。私の友人は、スミラールの質問を解決するためにこのコードを必要としています。

Answer 1

それは典型的な宿題の質問のように聞こえます。

しかし、それほど難しくはありません。

入力リスト上の単純な再帰関数が実行されます。関数の成分は、タスクの説明：単純なセット操作で既に言及されています。

宿題の場合、これが適用されます。宿題の質問の典型的な戦略は、最初にソリューションの試みを示さなければならないことです。これは、少なくともアルゴリズムのほぼ正しい定式化またはほぼ機能するコードである必要があります。その後、リスパーは仕上げの仕上げを手伝うかもしれません...

さて、時間が経ち、解決策はありません。

したがって、ここに共通のLISPを使用しているものがあります：

3つの機能が必要です。

最初の関数は、ペアのセットに単一のペアを追加します。ペアはリストです。ペアのセットはペアのリストです。ペアの場合、2つのセットを計算します。同等のペアのセットと、同等ではないペアのセットです。入力ペアと同等のペアを1つのセットに組み合わせます。

(defun equiv-add (e l)
  (let ((l- (remove-if     (lambda (i) (intersection e i)) l))
        (l+ (remove-if-not (lambda (i) (intersection e i)) l)))
    (cons (remove-duplicates (reduce #'union (cons e l+)))
          l-)))

2番目の関数は、結果にペアのセットの各ペアを追加します。それらを呼び出すことによってそれらを追加します。

(defun equiv-aux (list result)
  (if (null list)
      result
    (equiv-aux (rest list)
               (equiv-add (first list)
                          result))))

3番目の関数は、入力セットと空の結果を使用して、equiv-auxを呼び出すだけです。さらに、結果サブリストを並べ替えます。

(defun equiv (list)
  (mapcar (lambda (el)
            (sort el #'string-lessp))
          (equiv-aux list '())))

呼び出しの例：

CL-USER 34 > (equiv '((a b) (c d) (e f) (f g) (a e)))
((A B E F G) (C D))

CL-USER 35 > (equiv '((a b) (a c) (d e) (e f) (c g) (g h))) 
((A B C G H) (D E F))