Lisp-set

LISP-セット

Common Lispは、セットデータ型を提供しません。 ただし、リストに対してセット操作を実行できる多くの機能を提供します。

さまざまな基準に基づいて、リスト内のアイテムを追加、削除、および検索できます。 ユニオン、インターセクション、セット差分などのさまざまなセット操作を実行することもできます。

LISPでのセットの実装

リストのようなセットは通常、コンスセルの観点から実装されます。 ただし、このまさに理由で、集合が大きくなるほど集合演算の効率は低下します。

*adjoin* 関数を使用すると、セットを作成できます。 アイテムとセットを表すリストを受け取り、そのアイテムと元のセット内のすべてのアイテムを含むセットを表すリストを返します。

*adjoin* 関数は、指定されたリスト内のアイテムを最初に検索し、見つかった場合は元のリストを返します。それ以外の場合は、 *car* をアイテムとして、 *cdr* が元のリストを指している新しいコンスセルを作成し、この新しいリストを返します。

*adjoin* 関数は、*：key *および*：test *キーワード引数も取ります。 これらの引数は、アイテムが元のリストに存在するかどうかを確認するために使用されます。

adjoin関数は元のリストを変更しないため、リスト自体に変更を加えるには、adjoinによって返される値を元のリストに割り当てるか、マクロ pushnew を使用してアイテムを追加する必要がありますセット。

例

main.lispという名前の新しいソースコードファイルを作成し、次のコードを入力します。

; creating myset as an empty list
(defparameter *myset *())
(adjoin 1* myset*)
(adjoin 2 *myset*)

; adjoin did not change the original set
;so it remains same
(write *myset*)
(terpri)
(setf *myset *(adjoin 1* myset*))
(setf *myset *(adjoin 2* myset*))

;now the original set is changed
(write *myset*)
(terpri)

;adding an existing value
(pushnew 2 *myset*)

;no duplicate allowed
(write *myset*)
(terpri)

;pushing a new value
(pushnew 3 *myset*)
(write *myset*)
(terpri)

あなたがコードを実行すると、それは次の結果を返します-

NIL
(2 1)
(2 1)
(3 2 1)

メンバーシップの確認

関数のメンバーグループを使用すると、要素がセットのメンバーであるかどうかを確認できます。

以下は、これらの関数の構文です-

member item list &key :test :test-not :key
member-if predicate list &key :key
member-if-not predicate list &key :key

これらの関数は、テストを満たす特定のアイテムの特定のリストを検索します。 そのような項目が見つからない場合、関数は* nil。*を返します。それ以外の場合、最初の要素として要素を持つリストの末尾が返されます。

検索はトップレベルでのみ行われます。

これらの関数は、述部として使用できます。

例

main.lispという名前の新しいソースコードファイルを作成し、次のコードを入力します。

(write (member 'zara '(ayan abdul zara riyan nuha)))
(terpri)
(write (member-if #'evenp '(3 7 2 5/3 'a)))
(terpri)
(write (member-if-not #'numberp '(3 7 2 5/3 'a 'b 'c)))

あなたがコードを実行すると、それは次の結果を返します-

(ZARA RIYAN NUHA)
(2 5/3 'A)
('A 'B 'C)

ユニオンを設定

ユニオン関数グループを使用すると、テストに基づいてこれらの関数の引数として提供された2つのリストで集合ユニオンを実行できます。

以下は、これらの関数の構文です-

union list1 list2 &key :test :test-not :key
nunion list1 list2 &key :test :test-not :key

*union* 関数は2つのリストを受け取り、いずれかのリストに存在するすべての要素を含む新しいリストを返します。 重複がある場合、メンバーのコピーが1つだけ返されるリストに保持されます。

*nunion* 関数は同じ操作を実行しますが、引数リストを破壊する場合があります。

例

main.lispという名前の新しいソースコードファイルを作成し、次のコードを入力します。

(setq set1 (union '(a b c) '(c d e)))
(setq set2 (union '(#(a b) #(5 6 7) #(f h))
   '(#(5 6 7) #(a b) #(g h)) :test-not #'mismatch)
)

(setq set3 (union '(#(a b) #(5 6 7) #(f h))
   '(#(5 6 7) #(a b) #(g h)))
)
(write set1)
(terpri)
(write set2)
(terpri)
(write set3)

あなたがコードを実行すると、それは次の結果を返します-

(A B C D E)
(#(F H) #(5 6 7) #(A B) #(G H))
(#(A B) #(5 6 7) #(F H) #(5 6 7) #(A B) #(G H))

ご注意ください

ユニオン関数は、3つのベクトルのリストに対して*：test-not＃ 'mismatch 引数がないと期待どおりに機能しません。 これは、リストがコンスセルで構成されており、値が一見同じように見えても、セルの *cdr 部分が一致しないため、LISPインタープリター/コンパイラーとまったく同じではないためです。 という訳だ;リストを使用して大きなセットを実装することはお勧めしません。 ただし、小さなセットには問題ありません。

交差点を設定

関数の共通部分グループを使用すると、テストに基づいてこれらの関数の引数として提供される2つのリストで共通部分を実行できます。

以下は、これらの関数の構文です-

intersection list1 list2 &key :test :test-not :key
nintersection list1 list2 &key :test :test-not :key

これらの関数は2つのリストを取り、両方の引数リストにあるすべての要素を含む新しいリストを返します。 いずれかのリストに重複エントリがある場合、冗長エントリが結果に表示される場合と表示されない場合があります。

例

main.lispという名前の新しいソースコードファイルを作成し、次のコードを入力します。

(setq set1 (intersection '(a b c) '(c d e)))
(setq set2 (intersection '(#(a b) #(5 6 7) #(f h))
   '(#(5 6 7) #(a b) #(g h)) :test-not #'mismatch)
)

(setq set3 (intersection '(#(a b) #(5 6 7) #(f h))
   '(#(5 6 7) #(a b) #(g h)))
)
(write set1)
(terpri)
(write set2)
(terpri)
(write set3)

あなたがコードを実行すると、それは次の結果を返します-

(C)
(#(A B) #(5 6 7))
NIL

交差機能は、交差の破壊的なバージョンです。つまり、元のリストを破壊する可能性があります。

差を設定

関数のset-differenceグループを使用すると、テストに基づいてこれらの関数への引数として提供される2つのリストに対してset-differenceを実行できます。

以下は、これらの関数の構文です-

set-difference list1 list2 &key :test :test-not :key
nset-difference list1 list2 &key :test :test-not :key

set-difference関数は、2番目のリストに表示されない最初のリストの要素のリストを返します。

例

main.lispという名前の新しいソースコードファイルを作成し、次のコードを入力します。

(setq set1 (set-difference '(a b c) '(c d e)))
(setq set2 (set-difference '(#(a b) #(5 6 7) #(f h))
   '(#(5 6 7) #(a b) #(g h)) :test-not #'mismatch)
)
(setq set3 (set-difference '(#(a b) #(5 6 7) #(f h))
   '(#(5 6 7) #(a b) #(g h)))
)
(write set1)
(terpri)
(write set2)
(terpri)
(write set3)

あなたがコードを実行すると、それは次の結果を返します-

(A B)
(#(F H))
(#(A B) #(5 6 7) #(F H))