一般的なサブセットアルゴリズムの問​​題

Question

次の問題があります。

私はアイテムのセットを持っています{a1, a2, a3, ... aN}。それらのアイテムのそれぞれには別のアイテムセットが含まれています{b1, b2, b3, ... bN}。私は、次の規則に該当B型オブジェクトのグループを取得したいと思いアルゴリズムの実行の結果として

a1 
    b4 
    b22 
    b40 
    b11 
    b9 
a2 
    b30 
    b23 
    b9 
    b4 
    b11 
a3 
    b22 
    b4 
    b60 
    b9 

：だから、最終的な結果は次のようになります

1. 場合a型オブジェクトの下にある複数のb型オブジェクトは、そのa型オブジェクトの下にのみ存在します。グループ化する必要があります。
2. 複数のbタイプオブジェクトが複数のaタイプオブジェクトで使用される場合は、それらもグループ化する必要があります。

例：

b4, b9 
b30, b23 

b40, b60, b11 and b22 shouldn't be grouped because there are no pairs for them. 

バイナリツリーなどのそれには存在しないデータ構造を、避けるためにいいだろうので、私は、C＃で、このアルゴリズムの実装を書くことになります、リンクリストなどがありますが、これは必須条件ではありません。これらのすべてを実装することもできます。

明確化：セットには、必要な数のオブジェクトを含めることができますが、それぞれ1個以下にすることができます。規則は、同じaタイプ内のbタイプのすべてのユニークなオブジェクトをグループ化する（1より大きい）べきであり、1つ以上のbタイプオブジェクトが1つ以上のaタイプオブジェクトに含まれる場合、それらはグループ化されるべきである。グループは可能な限り大きくする必要があります。

実際の生活の例：ウェブページはある型およびそれらのページで使用されるCSSファイルは、B型です。ページの読み込みを高速化するためには、できるだけサーバーへの要求を少なくしたいので、CSSファイルを結合しますが、少数のページでのみ使用されるファイルは結合したくありませんキャッシュされ、再度ダウンロードする必要はありません。

Answer 1

まず、すべてのbタイプのアイテムを、そのbタイプのアイテムを含むaタイプのアイテムのセットに関連付けるマップを作成します。あなたの例では

、あなたが買ってあげる：

B4：{A1、A2、A3}

B9：{A1、A2、A3}

B11：{A1、A2}

B22：{A1、A3}

B23：{A2}

B30：{A2}

B40：{A1}

B60を：{A3}

A型オブジェクト内のすべてのB型オブジェクトをスキャンし、このマップを作成し、そしてB型オブジェクトは無しを有する場合関連付けのために、マップ内にエントリを作成します。ただし、a型オブジェクトをb型オブジェクトに関連付けられたセットに追加します。

次に、可能なすべての組（O（n2））を比較します。 2つのbタイプのオブジェクトが同じタイプのオブジェクトのセットを持つ場合は、それらを結合します。

マップ上で1対のネストループとして実装されます（I = 1 TO N-1、J = N + 1 TO N）。

2つのセットを比較するには、セットライブラリと比較演算子を使用します。

a型オブジェクトを小さな整数で表すことができる場合は、そのセットをビット配列として表現できます。これは、コンパクトで素早く比較することができます。