Разрывать-устанавливать леса в альтернативной реализации 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 (), так как требуется взять список узлов и значение (не просто узел) в качестве параметров. Find (set, value) будет прототипом.

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

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

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

Answer 1

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

Если вы умеете читать 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 s, а Find должен принимать аргумент Node.

Answer 2

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

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

Answer 3

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

Итак, функция find должна принимать один параметр узла и выглядеть следующим образом:

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

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