コンテンツにスキップ

0451: 半順序としての多重集合包含

問題

多重集合（要素の重複を許す集合）を表すクラス Multiset を実装してください。 Multiset(items) はイテラブル items の要素とその出現回数を記録します。

比較演算子は、多重集合の包含関係で定義します。 多重集合 \(A\) と \(B\) について、どの要素 \(x\) についても \(A\) における \(x\) の重複度が \(B\) における重複度以下であるとき、\(A \subseteq B\) と定めます。

  • __eq__：すべての要素の重複度が一致するときに限り True を返します。
  • __le__：\(A \subseteq B\) のときに限り True を返します。
  • __lt__：\(A \subseteq B\) かつ \(A \ne B\) のときに限り True を返します。

この包含関係は半順序であり、全順序ではありません。 つまり a <= b と b <= a の両方が False になる対（比較不能な対）が存在します。 数値の大小から類推すると「<= が False なら > が成り立つ」と考えがちですが、この推論は半順序では成り立ちません。 「例」の後半でこのことを確認します。

制約

  • Multiset のコンストラクタは任意のイテラブルを受け取ります。引数を省略した場合は空の多重集合とします。
  • 要素はハッシュ可能とします。要素間の順序は仮定しません（ソートできない要素も扱えるようにします）。
  • 比較相手が Multiset でない場合、各比較メソッドは NotImplemented を返します。
  • __ge__ と __gt__ を自分で定義してはいけません。Python が反射版のメソッド（a >= b に対する b.__le__(a) など）を呼び出すことを利用します。
  • functools.total_ordering を使ってはいけません。このデコレータは全順序を仮定するため、比較不能な対で誤った結果を返します。

例

>>> a = Multiset("aab")
>>> b = Multiset("aabb")
>>> a <= b
True
>>> a < b
True
>>> b <= a
False
>>> a <= a
True
>>> a < a
False
>>> b >= a
True
>>> Multiset("aba") == Multiset("aab")
True
>>> Multiset("ab") == Multiset("aab")
False
>>> c = Multiset("abc")
>>> a <= c
False
>>> c <= a
False
>>> a == c
False

最後の 3 行が比較不能な対です。 a は 'a' を 2 個持ちますが c は 1 個しか持たず、c は 'c' を持ちますが a は持ちません。 そのため、どちらの向きの包含も成り立ちません。

発展

  • 交わり __and__（重複度ごとの最小）と結び __or__（重複度ごとの最大）を追加してください。この 2 つの演算により、多重集合の全体は束（lattice）になります。a & b <= a や a <= a | b が任意の対で成り立つことを確認してください。
  • 多重集合和 __add__（重複度の和）を追加し、a <= a + b が成り立つことを確認してください。

参考