多重集合（バッグ）とは：定義・性質・応用

定義と表記法

多重集合は、同値な二つの方法で記述できる。一つは、たとえば {a, a, b, b, b, c} のように、繰り返しを含めて要素を列挙する方法である。もう一つは、可能な各要素 x に対して、その要素 x が何個含まれるかを示す非負整数 m(x) を対応させる重複度関数 m を用いる方法である。上の例では、m(a)=2、m(b)=3、m(c)=1 となる。この重複度関数は、要素の個数、重み、頻度と呼ばれることもある。表記は一定ではなく、繰り返しを含む波括弧、形式和、または重複度を示す縦線などが用いられる。「バッグ」という語は、出現順序ではなく、個数を伴う順序なしの所属を強調する。

基本演算と関係

多重集合に対する演算は通常の集合の演算を一般化したものだが、重複度を考慮しなければならない。代表的な演算には次のものがある。

• 和（多重集合の和）：多くの場合、要素の重複度を、二つの対象における重複度の最大値とする。
• 和の加法（互いに素な和または加算）：重複度を加える。異なる情報源から得た個数を統合する際に有用である。
• 共通部分：重複度を、対象となる多重集合の重複度の最小値とする。
• 差：重複度を減算し、個数が負にならないよう零を下限とする。

どの定義を用いるかは文脈に依存する。代数的な構成では重複度の加算が用いられることが多く、束論的な扱いでは最大値・最小値の規則が好まれる。重複度が位置に依存しない反復を表すとき、多重集合は順序なしタプルの一般化とみなすことができる。これらの見方を比較する形式的な議論はこちらを参照。

数え上げと多重集合係数

多重集合は、繰り返しを許す数え上げ問題の中心的な概念である。相異なる n 種類の要素から、順序を区別せず重複を許して r 個を選ぶ場合、異なる r 要素多重集合の数は重複組合せの数に等しい。この個数の標準的な閉形式は「n+r−1 個から r 個を選ぶ」と表され、しばしば C(n+r−1, r) と書かれる。この量は多重集合係数と呼ばれることがあり、((n r)) のような特別な表記を用いる場合もある。これらの公式は、同一の物体を区別された箱へ配分する問題から、単語を作るための文字の多重集合を選ぶ問題まで、幅広く使われる。

歴史、表現と可視化

反復された品目を数えるという考え方は組合せ論において古くから存在したが、多重集合という明示的な概念とバッグという用語は、集合論や代数構造が拡張された20世紀により体系化された。多重集合は、異なる要素とその重複度を列挙することで簡潔に表現できる。また、頻度を示すヒストグラム形式の図で表すこともでき、重複度を明確にするためにはヒストグラムや棒グラフが一般的な視覚的補助となる。図解も参照。コンピュータによる実装では、多重集合は要素から個数への連想配列やマップとして格納されることが多い。

用途、例と重要な区別

多重集合は多くの実用的状況をモデル化する。例として、同一品目が複数存在する在庫、整数の素因数の多重集合、重複行を保持するデータベース問合せ結果のバッグ意味論、形式言語理論および化学反応モデリングにおける多重集合書換え系がある。多重集合は順序を無視する点で列やタプルと異なり、重複度が重要である点で単純な集合と異なる。等しさを考える際には、すべての要素について重複度が一致することを要求する厳密な等しさを採用できるほか、応用に応じて何らかの正規化後の同値性を考えることもできる。より技術的な議論や形式的性質については、組合せ論および代数的データ型の入門資料、集合についての資料、重複度関数についての資料を参照できる。

参考文献・さらに読むには

多重集合は小規模ながら柔軟な集合の一般化である。集合に基づく考え方のなじみ深い直観の多くを保ちながら、個数を記録する簡明な方法を提供する。数学的背景、アルゴリズム上の実装、各分野での応用については、多重集合を組合せ論的かつ代数的に扱う入門資料や概説を参照するとよい。