Un ensemble trouver un algorithme

Question

J'ai des milliers de lignes de 1 à 100 numéros, chaque ligne définit un groupe de nombres et une relation entre eux. Je dois obtenir les ensembles de nombres connexes.

Petit exemple: Si j'ai cette 7 lignes de données

T1 T2 
T3 
T4 
T5 
T6 T1 
T5 T4 
T3 T4 T7 

je besoin d'un algorithme pas si lent à savoir que les jeux sont ici:

T1 T2 T6 (because T1 is related with T2 in the first line and T1 related with T6 in the line 5) 
T3 T4 T5 T7 (because T5 is with T4 in line 6 and T3 is with T4 and T7 in line 7) 

mais quand vous avez très les grands ensembles sont douloureusement lents à faire une recherche d'un T (x) dans chaque grand ensemble, et font des unions d'ensembles ... etc

Avez-vous un indice pour le faire dans un homme pas si brutal ner? J'essaye de faire ceci en Python. Traitez vos numéros T1, T2, etc. comme des sommets de graphique.

Answer 1

Une fois que vous avez construit la structure de données, exactement quelles requêtes voulez-vous courir contre elle? Montrez-nous votre code existant. Qu'est-ce qu'un T (x)? Vous parlez de "groupes de nombres" mais vos données d'échantillon montrent T1, T2, etc; S'il vous plaît, expliquez.

Avez-vous lu ceci: http://en.wikipedia.org/wiki/Disjoint-set_data_structure

Essayez de regarder cette implémentation Python: http://code.activestate.com/recipes/215912-union-find-data-structure/

OU vous pouvez arrimer quelque chose assez simple et compréhensible vous, par exemple

[Mise à jour: totalement nouveau code]

class DisjointSet(object): 

    def __init__(self): 
     self.leader = {} # maps a member to the group's leader 
     self.group = {} # maps a group leader to the group (which is a set) 

    def add(self, a, b): 
     leadera = self.leader.get(a) 
     leaderb = self.leader.get(b) 
     if leadera is not None: 
      if leaderb is not None: 
       if leadera == leaderb: return # nothing to do 
       groupa = self.group[leadera] 
       groupb = self.group[leaderb] 
       if len(groupa) < len(groupb): 
        a, leadera, groupa, b, leaderb, groupb = b, leaderb, groupb, a, leadera, groupa 
       groupa |= groupb 
       del self.group[leaderb] 
       for k in groupb: 
        self.leader[k] = leadera 
      else: 
       self.group[leadera].add(b) 
       self.leader[b] = leadera 
     else: 
      if leaderb is not None: 
       self.group[leaderb].add(a) 
       self.leader[a] = leaderb 
      else: 
       self.leader[a] = self.leader[b] = a 
       self.group[a] = set([a, b]) 

data = """T1 T2 
T3 T4 
T5 T1 
T3 T6 
T7 T8 
T3 T7 
T9 TA 
T1 T9""" 
# data is chosen to demonstrate each of 5 paths in the code 
from pprint import pprint as pp 
ds = DisjointSet() 
for line in data.splitlines(): 
    x, y = line.split() 
    ds.add(x, y) 
    print 
    print x, y 
    pp(ds.leader) 
    pp(ds.group) 

et voici la sortie de la dernière étape:

T1 T9 
{'T1': 'T1', 
'T2': 'T1', 
'T3': 'T3', 
'T4': 'T3', 
'T5': 'T1', 
'T6': 'T3', 
'T7': 'T3', 
'T8': 'T3', 
'T9': 'T1', 
'TA': 'T1'} 
{'T1': set(['T1', 'T2', 'T5', 'T9', 'TA']), 
'T3': set(['T3', 'T4', 'T6', 'T7', 'T8'])} 

Answer 2

Deux nombres apparaissant ensemble sur une ligne sont joints par un bord. Ensuite, votre problème revient à trouver tous les connected components dans ce graphique. Vous pouvez le faire en commençant par T1, puis en effectuant une recherche en largeur ou en profondeur pour trouver tous les sommets accessibles à partir de ce point. Marquer tous ces sommets comme appartenant à la classe d'équivalence T1. Recherchez ensuite le prochain sommet non marqué Ti, trouvez tous les nœuds encore non marqués à partir de là, et étiquetez-les comme appartenant à la classe d'équivalence Ti. Continuez jusqu'à ce que tous les sommets soient marqués. Pour un graphe avec n sommets et arêtes e, cet algorithme nécessite O (e) temps et espace pour construire les listes d'adjacence, et O (n) temps et espace pour identifier tous les composants connectés une fois que la structure du graphe est construit.

Answer 3

Vous pouvez utiliser une structure de données de syndicalisation pour atteindre cet objectif.

Le pseudo-code pour un tel algorithme est la suivante:

func find(var element) 
    while (element is not the root) element = element's parent 
    return element 
end func 

func union(var setA, var setB) 
    var rootA = find(setA), rootB = find(setB) 
    if (rootA is equal to rootB) return 
    else 
    set rootB as rootA's parent 
end func 

(Tiré de http://www.algorithmist.com/index.php/Union_Find)

Answer 4

Vous pouvez modéliser un groupe à l'aide d'un set. Dans l'exemple ci-dessous, j'ai placé l'ensemble dans une classe Group pour qu'il soit plus facile de conserver des références et de suivre un élément notionnel 'head'.

class Group: 
    def __init__(self,head): 
     self.members = set() 
     self.head = head 
     self.add(head) 
    def add(self,member): 
     self.members.add(member) 
    def union(self,other): 
     self.members = other.members.union(self.members) 

groups = {} 

for line in open("sets.dat"): 
    line = line.split() 
    if len(line) == 0: 
     break 
    # find the group of the first item on the row 
    head = line[0] 
    if head not in groups: 
     group = Group(head) 
     groups[head] = group 
    else: 
     group = groups[head] 
    # for each other item on the row, merge the groups 
    for node in line[1:]: 
     if node not in groups: 
      # its a new node, straight into the group 
      group.add(node) 
      groups[node] = group 
     elif head not in groups[node].members: 
      # merge two groups 
      new_members = groups[node] 
      group.union(new_members) 
      for migrate in new_members.members: 
       groups[migrate] = group 
# list them 
for k,v in groups.iteritems(): 
    if k == v.head: 
     print v.members 

sortie est:

set(['T6', 'T2', 'T1']) 
set(['T4', 'T5', 'T3']) 

Answer 5

Comme Jim souligné ci-dessus, vous êtes à la recherche essentiellement pour la connected components d'un graphe non orienté simple où les noeuds sont vos entités (T1, T2 et ainsi), et les arêtes représentent les relations par paires entre eux. Une implémentation simple pour la recherche de composants connectés est basée sur la recherche en largeur: vous démarrez un BFS à partir de la première entité, trouvez toutes les entités liées, puis démarrez un autre BFS de la première entité non encore apparue et ainsi de suite jusqu'à ce que vous les trouviez tout. Une mise en œuvre simple BFS ressemble à ceci:

class BreadthFirstSearch(object): 
    """Breadth-first search implementation using an adjacency list""" 

    def __init__(self, adj_list): 
     self.adj_list = adj_list 

    def run(self, start_vertex): 
     """Runs a breadth-first search from the given start vertex and 
     yields the visited vertices one by one.""" 
     queue = deque([start_vertex]) 
     visited = set([start_vertex]) 
     adj_list = self.adj_list 

     while queue: 
      vertex = queue.popleft() 
      yield vertex 
      unseen_neis = adj_list[vertex]-visited 
      visited.update(unseen_neis) 
      queue.extend(unseen_neis) 

def connected_components(graph): 
    seen_vertices = set() 
    bfs = BreadthFirstSearch(graph) 
    for start_vertex in graph: 
     if start_vertex in seen_vertices: 
      continue 
     component = list(bfs.run(start_vertex)) 
     yield component 
     seen_vertices.update(component) 

Ici, adj_list ou est une structure de données de liste de contiguïté, fondamentalement, il vous donne les voisins d'un sommet donné dans le graphique. Pour le construire à partir de votre fichier, vous pouvez le faire:

adj_list = defaultdict(set) 
for line in open("your_file.txt"): 
    parts = line.strip().split() 
    v1 = parts.pop(0) 
    adj_list[v1].update(parts) 
    for v2 in parts: 
     adj_list[v2].add(v1) 

Ensuite, vous pouvez exécuter:

components = list(connected_components(adj_list)) 

Bien sûr, la mise en œuvre l'ensemble algorithme en Python pur tend à être plus lent que d'une mise en œuvre en C avec une structure de données graphique plus efficace. Vous pourriez envisager d'utiliser igraph ou une autre bibliothèque de graphes comme NetworkX pour faire le travail à la place. Les deux bibliothèques contiennent des implémentations pour la recherche de composants connectés; dans igraph, il se résume à ceci (en supposant que votre fichier ne contient pas de lignes avec des entrées uniques, seules les entrées par paires sont acceptées):

>>> from igraph import load 
>>> graph = load("edge_list.txt", format="ncol", directed=False) 
>>> components = graph.clusters() 
>>> print graph.vs[components[0]]["name"] 
['T1', 'T2', 'T6'] 
>>> print graph.vs[components[1]]["name"] 
['T3', 'T4', 'T5'] 

Disclaimer: Je suis l'un des auteurs de igraph