partition une liste d'ensembles par des éléments partagés

Question

Voici le jist du problème: Étant donné une liste de jeux, tels que:

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

Retour liste des groupes des ensembles, tels que les ensembles qui ont une responsabilité partagée élément sont dans le même groupe.

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

Notez le stickeyness - l'ensemble (6,12,13) ​​ne dispose pas d'un élément partagé avec (1,2,3), mais ils se mettre dans le même groupe en raison de (5,2 , 6).

Pour compliquer les choses, je dois mentionner que je n'ai pas vraiment ces jeux propres, mais plutôt une table DB avec plusieurs millions de lignes qui ressemble à:

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

et ainsi de suite. Donc, j'aimerais un moyen de le faire en SQL, mais je serais heureux avec une orientation générale pour la solution.

EDIT: Changé les noms de colonnes de table à (élément, set_id) au lieu de (clé, group_id), pour rendre les termes plus cohérente. Notez que la réponse de Kev utilise les anciens noms de colonnes.

Answer 1

Le problème est exactement le calcul des composants connectés d'un hypergraphe: les entiers sont les sommets, et les ensembles sont les hypercharges. Une manière habituelle de calcul des composantes connexes est en les inondant l'un après l'autre:

• pour tout i = 1 à N, faites:
• si i a été marquée par certains j < i, puis continuer (Je veux dire passer à la suivante i)
• autre flood_from (i, i)

où flood_from (i, j) serait définie comme

• pour chaque ensemble S contenant i, s'il n'est pas déjà marqué par j alors:
• étiquette S par j et pour chaque élément k de S, si k n'est pas déjà étiqueté par j, alors l'étiquette par j, et appelez flood_from (k, j)

Les étiquettes des ensembles vous donnent alors les composants connectés que vous recherchez.

---

En termes de bases de données, l'algorithme peut être exprimé comme suit: vous ajoutez une colonne TAG à votre base de données, et vous calculer la composante connexe de jeu i en faisant

• S = sélectionner tous les les lignes où set_id == i
• ensemble TAG à i pour les lignes de S
• S « = sélectionner toutes les lignes où TAG est pas défini et où l'élément est dans l'élément (S)
• alors que S » est pas vide , faites
• ---- définir TAG à i pour les lignes de S '
• ---- S ''= sélectionner toutes les lignes où TAG est pas défini et où l'élément est dans l'élément (S')
• - --- S = S union S '
• ---- S' = S ''
• retour set_id (S)

---

Une autre façon (théorique) de présenter cet algorithme serait pour dire que vous cherchez les points fixes d'une cartographie:

• si A = {A , ..., A n } est un ensemble d'ensembles, définissent union (A) = A union ...Une union _n
• si K = {k , ..., k _p} est un ensemble de nombres entiers, définie incidence (K) = l'ensemble des ensembles qui se coupent K

Ensuite, si S est un ensemble, la composante connexe de S est obtenu par itération (incidence) o (union) sur S jusqu'à un point fixe est atteint:

1. K = S
2. K »= incidence (union (K)).
3. si K == K 'puis retour K, sinon K = K' et aller à 2.

Answer 2

Vous pourriez penser comme un problème graphique où l'ensemble (1,2,3) est relié à l'ensemble (5,2,6) via le 2. Et puis utiliser un algorithme standard pour affiner la sous connectée graphiques.

Voici une implémentation Python rapide:

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] 

sortie:

[[]] 
[[6, 7, 8], [10, 11, 12], [7, 10, 13], [12]] 
[[1, 2, 3], [2, 4, 5]] 

Answer 3

Cela est probablement assez inefficace, mais il devrait fonctionner, au moins: Commencez par une touche, sélectionnez tous les groupes contenant cette touche, sélectionnez toutes les clés de ces groupes, sélectionnez tous les groupes contenant ces clés, etc., et dès qu'une étape n'ajoute aucune nouvelle clé ou groupe, vous avez une liste de tous les groupes d'un sous-graphe. Exclure ceux-ci et répétez depuis le début jusqu'à ce qu'il ne vous reste plus de données.

En termes de SQL cela aurait besoin d'une procédure stockée, je pense. WITH RECURSIVE peut vous aider d'une manière ou d'une autre, mais je n'en ai pas encore l'expérience, et je ne suis pas sûr qu'il soit disponible sur votre backend DB.

Answer 4

Après avoir réfléchi à ce un peu plus, je suis venu avec ceci:

1. Créer une table appelée groups avec des colonnes (group_id, set_id)
2. Trier la table sets par element. Maintenant, il devrait être facile de trouver des éléments en double.
3. Itérer à travers la table des jeux, et quand vous trouvez un élément en double faire:
   1. si l'un des champs set_id existe dans le tableau groups, ajoutez l'autre avec le même group_id.
   2. S'il n'existe aucun des set_id dans la table groups, générez un nouvel ID de groupe et ajoutez les deux set_id à la table groups.

En fin de compte je devrais avoir une table groups contenant tous les ensembles.

Ce n'est pas un SQL pur, mais cela ressemble à O (nlogn), donc je suppose que je peux vivre avec ça.

Matt's answer semble plus correct, mais je ne sais pas comment l'implémenter dans mon cas.