5

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

(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-unionunionintersectionremove-duplicates

どうもありがとう！

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

4

1 に答える 1

4

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

とはいえ、それほど難しいことではありません。

入力リストに対する単純な再帰関数で十分です。関数の構成要素は、タスクの説明で既に言及されています: 単純な集合操作。

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

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

Common Lisp を使った例を次に示します。

3 つの関数が必要です。

最初の関数は、ペアのセットに 1 つのペアを追加します。ペアはリストです。ペアのセットはペアのリストです。ペアについては、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 番目の関数は、一連のペアの各ペアを結果に追加します。EQUIV-ADD を呼び出して追加します。

(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))
于 2010-05-03T17:57:58.620 に答える