Алгоритм поиска объединений множеств

Question

У меня есть тысячи строк от 1 до 100 чисел, каждая строка определяет группу чисел и отношения между ними. Мне нужно получить наборы связанных номеров.

Маленький пример: Если у меня есть эти 7 строк данных

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

Мне нужен не очень медленный алгоритм, чтобы знать, что наборы здесь:

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)

но если у вас очень большие наборы, мучительно медленно выполнять поиск T (x) в каждом большом наборе и объединять множества ... и т. Д.

У вас есть подсказка сделать это не так грубо?

Я пытаюсь сделать это на Python.

Answer 1

Как только вы построите структуру данных, какие именно запросы вы хотите выполнить к ней?Покажите нам свой существующий код.Что такое Т (х)?Вы говорите о «группах чисел», но ваши данные показывают T1, T2 и т. Д .;пожалуйста, объясните.

Вы читали это: http://en.wikipedia.org/wiki/Disjoint-set_data_structure

Попробуйте взглянуть на эту реализацию Python: http://code.activestate.com/recipes/215912-union-find-data-structure/

ИЛИ вы можете набросать что-то довольно простое и понятное самостоятельноНапример,

[Обновление: совершенно новый код]

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)

и вот результат последнего шага:

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

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

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

Answer 3

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

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

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)

Answer 4

Как отмечалось выше Джим , вы, по сути, ищете связанных компонентов простого неориентированного графа, где узлами являются ваши сущности (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']

Отказ от ответственности: я один из авторов igraph

Answer 5

Вы можете смоделировать группу, используя set. В приведенном ниже примере я поместил набор в класс 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'])