複合多対多リレーション？

Question

私は解析する方法がわからない複雑なデータ構造を持つプロジェクトに取り組んでいます。私は解決策を構築しようとしていますが、私が思いつくそれぞれのアイデアは、100％の精度がないと感じています。既によく知られていて、テストされた方法が既に存在するなら、私はそれに頼ることができます。だからここ

は例です：

は店がプロモーションのリストを持っている想像し、各プロモーションが、それは他のプロモーションと接続できるかどうかの、それ独自のリストを持っています。私はお互いにつながるプロモーションの積み重ねを考え出す必要があります。

は、だから私は、私はとスタックしたプロモーション私に告げるリストを取得しますプロモーション、A、B、C、Dを持って言うことができますどのキャンペーン：

A - > B = S（スタッカブル）

- > C = N（非積み重ね可能）

A - > D = S

Bは、そのリストを有し、Dは、そのリストを有することになります。私はNを持たないということは積み重ねられることを意味するとは思えませんが、Sを持たないということは積み重ねられないことを意味します。 1から無限のプロモーションまで、どこにでもあります。

可能なすべてのプロモーションの組み合わせを入手できるようにする必要があります。結局、私はすべての組み合わせの配列（できればユニークな組み合わせ）が必要ですが、すべての組み合わせがリストされていれば、ユニークでなくても問題ありません。そのような問題の名前を知っていて名前だけで答えることができたら、私の質問を編集する必要はありません。

Answer 1

これは、clique problemとして公式化できると思います。

プロモーションが頂点であり、プロモーションを積み重ねることができる場合は、2つの頂点間にエッジがあるグラフを作成する必要があります。可能なプロモーションは完全なサブグラフまたはクリークであり、サブグラフでは各頂点が互いに頂点に接続されているサブグラフです。

これはNP完全な問題ですが、システムがそれほど大きくなければ、解決することは可能です。

ブルートフォースアルゴリズムはかなり単純です。特殊なケースが2つあります。

1. まず頂点が2つの頂点を接続する全てのエッジが残り

   k = 2 .. (number of vertices) 
       v in vertices 
       if (v.neighbors.size >= k) 
        s in distinct combination of k neighbors of v and v 
        if each vertex in s has a link to other vertices in s add s to the list 
   

   として、次いでクリーク（二キャンペーンのリスト）

あるクリーク（単独で、各プロモーション）

あります組み合わせの数が指数関数的に増加するにつれて、多くのリンクがあればアルゴリズムが遅くなることがわかります。