2

序章

グラフ内のノードでいくつかの分類を行おうとすると（レンダリングが異なります）、次の問題に直面しました。

問題

要素のスーパーセットとその素でないサブセットS = {0, 1, ... M}の数が与えられた場合、と呼ばれるセットの分割を見つけるための最良のアルゴリズムは何ですか？nT_i0 <= i < nSP

P = Sは、元のスーパーセットのすべての互いに素なパーティションの和集合であり、すべての要素について、すべてが「元の」セットの中で同じ「親」のリストを持つようになります。P_jS0 <= j < Mx in P_jxT_i

例

S = [1, 2, 3, 4, 5, 6,   8, 9]

T_1 = [1, 4]
T_2 = [2, 3]
T_3 = [1, 3, 4]

したがって、すべてP_jは次のようになります。

P_1 = [1, 4] # all elements x have the same list of "parents": T_1, T_3
P_2 = [2] # all elements x have the same list of "parents": T_2
P_3 = [3] # all elements x have the same list of "parents": T_2, T_3
P_4 = [5, 6, 8, 9] #  all elements x have the same list of "parents": S (so they're not in any of the P_j

質問

  1. すべてP_jのsとその「親」のリストを計算するためのPythonパッケージの優れた関数/クラスは何ですか？理想的にはとに制限されnumpyていscipyますか？おそらく、それを実行する関数がすでに存在します
  2. それらのパーティションと、それぞれの「親」のリストP_jを見つけるための最良のアルゴリズムは何ですか？注意しましょうT_0 = S

力ずくのアプローチは、セットの2つの組み合わせをすべて生成しT、それらを最大3つの互いに素なセットに分割し、それらをセットのプールに追加して、結果のすべてのが互いに素にTなるまでプロセスを繰り返すことだと思いますT。私たちは答えに到達しました-セットのPセット。少し問題があるのは、そこに行く途中ですべての「親」をキャッシュすることです。

動的計画法のアプローチを使用してアルゴリズムを最適化できると思います。

注：私は（MathJaxを介して）ラテックスで数学の部分を書くのが好きでしたが、残念ながらこれはアクティブ化されていません:-(

4

2 に答える 2

1

以下は線形時間（Tsの要素数）である必要があります。

from collections import defaultdict

S = [1, 2, 3, 4, 5, 6,   8, 9]

T_1 = [1, 4]
T_2 = [2, 3]
T_3 = [1, 3, 4]

Ts = [S, T_1, T_2, T_3]

parents = defaultdict(int)
for i, T in enumerate(Ts):
    for elem in T:
        parents[elem] += 2 ** i

children = defaultdict(list)
for elem, p in parents.items():
    children[p].append(elem)

print(list(children.values()))

結果：

[[5, 6, 8, 9], [1, 4], [2], [3]]
于 2012-12-22T23:01:12.497 に答える
1

これを行う方法は、M × nブール配列Inを作成することです。すべてのセットをスキャンし、の対応するビットをマークすることにより、の要素をの整数インデックスにマップできる場合は、でそれを構築できます。In(i, j) = Si ∈ TjO(Σj|Tj|)SO(1)TIn

次に、行を2進数のビットに連結することにより、各要素の「署名」をi直接読み取ることができます。シグニチャは、正確には、探しているパーティションの同値関係です。Inin

ちなみに、私は数学のマークアップについてあなたと完全に同意しています。おそらく、新しいキャンペーンを開始する時が来たのでしょう。

于 2012-12-22T23:08:30.657 に答える