5

問題の要点は次のとおりです。次のようなセットのリストが与えられます。

[ (1,2,3), (5,2,6), (7,8,9), (6,12,13), (21,8,34), (19,20) ]

共有要素を持つセットが同じグループにあるように、セットのグループのリストを返します。

[ [ (1,2,3), (5,2,6), (6,12,13) ], [ (7,8,9), (21,8,34) ], [ (19,20) ] ]

粘着性に注意してください - セット (6,12,13)​​ には (1,2,3) との共有要素はありませんが、(5,2,6) のために同じグループに入れられます。

問題を複雑にするために、私は実際にはこれらのきちんとしたセットを持っているわけではなく、次のような数百万行の DB テーブルを持っていることに言及する必要があります。

element | set_id
----------------
1       | 1
2       | 1
3       | 1
5       | 2
2       | 2
6       | 2

等々。だから私はSQLでそれを行う方法が大好きですが、解決策の一般的な方向性に満足しています.

EDIT : テーブルの列名を (key, group_id) ではなく (element, set_id) に変更して、用語の一貫性を高めました。Kev の回答では古い列名が使用されていることに注意してください。

4

4 に答える 4

6

問題は、まさにハイパーグラフの連結成分の計算です。整数は頂点であり、集合はハイパーエッジです。連結成分を計算する通常の方法は、それらを次々にフラッディングすることです。

  • すべての i = 1 から N に対して、次のようにします。
  • i がいくつかの j < i によってタグ付けされている場合、続行します (次の i にスキップすることを意味します)
  • そうでなければflood_from(i,i)

どこで flood_from(i,j) は次のように定義されます

  • i を含む各セット S について、まだ j によってタグ付けされていない場合:
  • S を j でタグ付けし、S の各要素 k に対して、k がまだ j でタグ付けされていない場合は、j でタグ付けし、flood_from(k,j) を呼び出します。

セットのタグは、探している接続されたコンポーネントを提供します。

データベースに関しては、アルゴリズムは次のように表現できます。データベースに TAG 列を追加し、次のようにしてセット i の連結成分を計算します。

  • S = set_id == i のすべての行を選択
  • S の行の TAG を i に設定します
  • S' = TAG が設定されておらず、要素が要素 (S) 内にあるすべての行を選択します
  • S' が空でない間、
  • ---- S' の行の TAG を i に設定します
  • ---- S'' = TAG が設定されておらず、要素が element(S') 内にあるすべての行を選択します
  • ---- S = S ユニオン S'
  • ---- S' = S''
  • set_id(S) を返す

このアルゴリズムを提示する別の (理論的な) 方法は、マッピングの固定点を探していると言うことです。

  • A = {A 1 , ..., A n } が集合の集合である場合、union(A) = A 1 union ... union A nを定義します。
  • K = {k 1 , ..., k p } が整数の集合である場合、incidents(K) = K と交差する集合の集合を定義します

次に、S が集合の場合、S の連結成分は、固定点に到達するまで S で (incidences)o(union) を反復することによって取得されます。

  1. K = S
  2. K' = 発生率 (ユニオン (K))。
  3. K == K' の場合は K を返し、そうでない場合は K = K' で 2 に進みます。
于 2008-10-07T21:46:23.557 に答える
1

セット (1,2,3) が 2 を介してセット (5,2,6) に接続されているグラフの問題と考えることができます。次に、標準アルゴリズムを使用して、接続されたサブグラフを微調整します。

これは簡単な python 実装です:

nodes = [ [1,2,3], [2,4,5], [6,7,8], [10,11,12], [7,10,13], [12], [] ]
links = [ set() for x in nodes ]

#first find the links
for n in range(len(nodes)):
    for item in nodes[n]:
        for m in range(n+1, len(nodes)):
            if (item in nodes[m]):
                links[n].add(m)
                links[m].add(n)

sets = []
nodes_not_in_a_set = range(len(nodes))

while len(nodes_not_in_a_set) > 0:
    nodes_to_explore = [nodes_not_in_a_set.pop()]
    current_set = set()
    while len(nodes_to_explore) > 0:
        current_node = nodes_to_explore.pop()
        current_set.add(current_node)
        if current_node in nodes_not_in_a_set:
            nodes_not_in_a_set.remove(current_node)
        for l in links[current_node]:
            if l not in current_set and l not in nodes_to_explore:
                nodes_to_explore.append(l)
    if len(current_set) > 0:
        sets.append(current_set)

for s in sets:
    print [nodes[n] for n in s]

出力：

[[]]
[[6, 7, 8], [10, 11, 12], [7, 10, 13], [12]]
[[1, 2, 3], [2, 4, 5]]
于 2008-10-07T15:12:03.303 に答える
0

これについてもう少し考えた後、私はこれを思いつきました：

  1. groups列を持つという名前のテーブルを作成します(group_id, set_id)
  2. setsで表を並べ替えますelement。これで、重複する要素を簡単に見つけることができるはずです。
  3. セット テーブルを反復処理し、重複する要素が見つかったら、次のようにします。
    1. set_idフィールドの 1 つがgroupsテーブルに存在する場合は、同じgroup_id.
    2. どちらもテーブルにset_id存在しない場合は、新しいグループ ID を生成し、両方の をテーブルgroupsに追加します。set_idgroups

最後に、groupsすべてのセットを含むテーブルが必要です。

これは純粋な SQL ではありませんが、O(nlogn) のように見えるので、それで問題ないと思います。

マットの答えはより正しいようですが、私の場合はそれを実装する方法がわかりません。

于 2008-10-07T15:59:22.133 に答える
0

これはおそらくかなり非効率的ですが、少なくとも動作するはずです: キーで開始し、そのキーを含むすべてのグループを選択し、それらのグループのすべてのキーを選択し、それらのキーを含むすべてのグループを選択します。ステップは新しいキーまたはグループを追加しません。1 つのサブグラフのすべてのグループのリストがあります。それらを除外し、データがなくなるまで最初から繰り返します。

SQLに関しては、これにはストアドプロシージャが必要になると思います。WITH RECURSIVE は何らかの形で役立つかもしれませんが、まだ経験がなく、DB バックエンドで利用できるかどうかもわかりません。

于 2008-10-07T15:16:14.967 に答える