Реализация системы несвязных множеств в Python - PullRequest
Новая
       33

Реализация системы несвязных множеств в Python

4 голосов
/ 23 февраля 2011

То, что я имею до сих пор, в значительной степени основано на странице 571 «Введение в алгоритмы» Кормена и др.

У меня есть класс Node в python, который представляет набор: 

class Node:
    def __init__(self, parent, rank = 0):
        self.parent = parent
        self.rank = rank

Эта реализация будет использовать List узлов в качестве леса (я открыт для более эффективных способов хранения наборов).

Initialize() возвращает список узлов, которые я буду хранить впеременная set и передача в другие функции.

Find ищет значение в лесу и возвращает набор, в котором оно появляется. Я решил использовать for s in range(len(set)):, чтобы в рекурсии я могсократить список наборов, передаваемых set[s:].

<code>def Find(set, value):
    for s in range(len(set)):
        if value != set[s].parent:
            set[s].parent = Find(set[s:], set[s].parent)
        return set[s]

Merge объединяет наборы в лесу, находя их и продвигая наборы с более высоким рейтингом.

<code>def Merge(set, value1, value2):
    set_val_1 = Find(set, value1)
    set_val_2 = Find(set, value2)
    if set_val_1.rank > set_val_2.rank:
        set_val_2.parent = set_val_1
    else:
        set_val_1.parent = set_val_2
        if set_val_1.rank == set_val_2.rank:
            set_val_2.rank += 1

Я получаю некоторые ошибки, когда я Find с и Merge с, а именно Find не возвращает правильный набор, и поэтому я не уверен, если Merge работает как надо.Буду признателен за помощь, чтобы убедиться, что функции реализованы правильно.

Ответы [ 5 ]

4 голосов
/ 23 февраля 2011

Вы смотрели на любые другие существующие реализации ?

2 голосов
/ 24 февраля 2011

Предполагается, что каждый узел инициализируется как собственный родитель: 

def Find(node):
    while node is not node.parent:
        node = node.parent
    return node
2 голосов
/ 23 февраля 2011

У меня нет последней редакции книги, но это не совсем похоже на непересекающийся лес.

Я думаю, что ваша ошибка - думать, что лес должен храниться вколлекция и что вам нужно пройти эту коллекцию, чтобы сделать операции на узлах.Удалите set из Merge() и Find() и внедрите Find() как 

def Find(n):
    if n != n.parent:
        n.parent = Find(n.parent)
    return n.parent

, как в книге.Затем добавьте MakeSet(), который возвращает один правильно инициализированный узел, и, возможно, функцию SameSet(): 

def SameSet(n1, n2):
    return Find(n1) == Find(n2)

Теперь у вас есть рабочая реализация несвязанного множества.

1 голос
/ 10 марта 2014

Используя эту реализацию в качестве отправной точки, я создал новый класс Python для обработки непересекающихся множеств, который также поддерживает постоянство с использованием MongoDb.

С моим классом вы должны бытьможет, например,:

  • Создать экземпляр UnionFind(), который по умолчанию использует встроенные словари python, и позже принять решение consolidate() о ваших результатах в коллекции MongoDb
  • Создайте экземпляр UnionFind из коллекции MongoDb и напрямую используйте его.

Возможно, вы захотите проверить код на github .

Cheers,Simone

0 голосов
/ 26 августа 2018

Страница Википедии предоставляет псевдокод для основных операций над структурой данных с несвязным множеством.Вот прямой порт в Python (использует сжатие путей и объединение по рангу): 

class Node:
    """Represents an element of a set."""
    def __init__(self, id):
        self.id = id
        self.parent = self
        self.rank = 0
        self.size = 1

    def __repr__(self):
        return 'Node({!r})'.format(self.id)


def Find(x):
    """Returns the representative object of the set containing x."""
    if x.parent is not x:
        x.parent = Find(x.parent)
    return x.parent


def Union(x, y):
    """Combines the sets x and y belong to."""
    xroot = Find(x)
    yroot = Find(y)

    # x and y are already in the same set
    if xroot is yroot:
        return

    # x and y are not in same set, so we merge them
    if xroot.rank < yroot.rank:
        xroot, yroot = yroot, xroot  # swap xroot and yroot

    # merge yroot into xroot
    yroot.parent = xroot
    xroot.size += yroot.size
    if xroot.rank == yroot.rank:
        xroot.rank = xroot.rank + 1

Демо: 

>>> a, b, c = map(Node, 'abc')
>>> Find(a), Find(b), Find(c)
(Node('a'), Node('b'), Node('c'))
>>> Find(a).size
1
>>> Union(a, b)
>>> Union(b, c)
>>> Find(a), Find(b), Find(c)
(Node('a'), Node('a'), Node('a'))
>>> Find(a).size
3
...