Объединение набора находит алгоритм

Как Jim указал выше, вы по существу ищете связанные компоненты простого неориентированного графа, где узлы - это ваши сущности (T1, T2 и так далее), а ребра представляют парные отношения между ними. Простая реализация поиска связанных компонентов основана на поиске по принципу "сначала в ширину": вы начинаете BFS с первой сущности, находите все связанные с ней сущности, затем начинаете другой BFS с первой еще не найденной сущности и так далее, пока не найдете их все. Простая реализация BFS выглядит так:

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)

Здесь adj_list или graph - это структура данных списка смежности, в основном она дает вам соседей данной вершины в графе. Чтобы собрать его из вашего файла, вы можете сделать следующее:

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)

Затем вы можете выполнить:

components = list(connected_components(adj_list))

Конечно, реализация всего алгоритма на чистом Python, как правило, медленнее, чем реализация на C с более эффективной структурой данных графа. Вы можете рассмотреть возможность использования igraph или другой библиотеки графов, например NetworkX, для выполнения этой работы. Обе библиотеки содержат реализации для поиска связанных компонентов; в igraph это сводится к следующему (при условии, что ваш файл не содержит строк с одиночными записями, принимаются только парные записи):

>>> 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: I am one of the authors of igraph

Вы можете смоделировать группу, используя набор . В приведенном ниже примере я поместил набор в класс Group, чтобы упростить сохранение ссылок на них и отслеживание некоторого условного элемента «головы».

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

Вывод:

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

Рассматривайте числа T1, T2 и т.д. как вершины графа. Любые два числа, появляющиеся вместе на линии, соединяются ребром. Тогда ваша задача сводится к поиску всех связных компонентов в этом графе. Вы можете сделать это, начав с точки T1, затем выполнить поиск в ширину или в глубину, чтобы найти все вершины, достижимые из этой точки. Пометьте все эти вершины как принадлежащие классу эквивалентности T1. Затем найдите следующую немаркированную вершину Ti, найдите все еще немаркированные вершины, достижимые из нее, и пометьте их как принадлежащие классу эквивалентности Ti. Продолжайте, пока все вершины не будут помечены.

Для графа с n вершинами и e ребрами этот алгоритм требует O(e) времени и места для построения списков смежности и O(n) времени и места для определения всех связных компонентов. после построения структуры графа.

Для достижения этой цели можно использовать структуру данных union find.

Псевдокод такого алгоритма выглядит следующим образом:

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

(Взято из http://www.algorithmist.com/index.php/Union_Find)