Разрывать-устанавливать леса в альтернативной реализации Python

Question

Я внедряю систему непересекающихся множеств в Python, но я попал в стену. Я использую древовидную реализацию для системы и реализую функции Find(), Merge() и Create() для системы.

Я внедряю систему рангов и сжатие путей для эффективности.

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

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

def Create(values):
    l = [Node(value) for value in values]
    return l

Функция Create принимает список значений и возвращает список единичных узлов, содержащих соответствующие данные.

Я думаю, что функция слияния будет выглядеть примерно так,

def Merge(set, value1, value2):
    value1Root = Find(set, value1)
    value2Root = Find(set, value2)
    if value1Root == value2Root:
        return
    if value1Root.rank < value2Root.rank:
        value1Root.parent = value2Root
    elif value1Root.rank > value2Root.rank:
        value2Root.parent = value1Root
    else:
        value2Root.parent = value1Root
        value1Root.rank += 1

но я не уверен, как реализовать функцию Find (), поскольку она должна принимать список узлов и значение (а не только узел) в качестве параметров. Найти (установить, значение) будет прототип.

Я понимаю, как реализовать сжатие пути, когда Node принимается в качестве параметра для Find(x), но этот метод меня отбрасывает.

Любая помощь будет принята с благодарностью. Спасибо.

Отредактировано для уточнения.

Answer 1

Очевидно merge Функция должна применяться к паре узлов.

Так find Функция должна принимать один параметр узла и выглядеть так:

def find(node):
    if node.parent != node:
        node.parent = find(node.parent)
    return node.parent

Также в Википедии есть псевдокод, который легко переводится на python.

Answer 2

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

Если вы можете читать C++, взгляните на мой взгляд на структуру данных; он скрывает фактические наборы от внешнего мира, представляя их только как числовые индексы в API. В Python это было бы что-то вроде

class DisjSets(object):
    def __init__(self, n):
        self._parent = range(n)
        self._rank = [0] * n

    def find(self, i):
        if self._parent[i] == i:
            return i
        else:
            self._parent[i] = self.find(self._parent[i])
            return self._parent[i]

    def union(self, i, j):
        root_i = self.find(i)
        root_j = self.find(j)
        if root_i != root_j:
            if self._rank[root_i] < self._rank[root_j]:
                self._parent[root_i] = root_j
            elif self._rank[root_i] > self._rank[root_j]:
                self._parent[root_j] = root_i
            else:
                self._parent[root_i] = root_j
                self._rank[root_j] += 1

(Не испытано.)

Если вы решите не следовать этому пути, клиент вашего кода действительно должен будет знать Nodeс и Find должен взять Node аргумент.

Answer 3

Поиск всегда делается на предмете. Find (элемент) определяется как возвращающий набор, к которому принадлежит элемент. Слияние как таковое не должно принимать узлы, слияние всегда занимает два элемента / набора. Объединение или объединение (item1, item2) должны сначала найти (item1) и find(item2), которые будут возвращать наборы, к которым принадлежит каждый из них. После этого меньший набор, представленный верхним деревом, должен быть добавлен к более высокому. Когда выдается находка, всегда прослеживайте путь и сжимайте его.

Протестированная реализация со сжатием пути здесь.