0

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）がプロトタイプになります。

ノードがFind（x）のパラメーターとして使用される場合にパス圧縮を実装する方法を理解していますが、このメソッドは私を失望させます。

どんな助けでも大歓迎です。ありがとうございました。

明確にするために編集。

4

3 に答える 3

2

このデータ構造の実装は、オペレーションunionとfindが、個々の互いに素なセットではなく、互いに素なセットのフォレストクラスのメソッドとして実装できることを理解すると、より簡単になります。

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

于 2012-02-28T20:06:51.357 に答える
1

明らかmergeに、関数はノードのペアに適用する必要があります。

したがって、find関数は単一ノードパラメータを取り、次のようになります。

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

また、ウィキペディアには、Pythonに簡単に翻訳できる擬似コードがあります。

于 2012-02-28T19:46:11.310 に答える
0

検索は常にアイテムに対して行われます。Find（item）は、アイテムが属するセットを返すものとして定義されます。合併自体はノードをとってはならず、合併は常に2つのアイテム/セットを取ります。マージまたはユニオン（item1、item2）は、最初にfind（item1）およびfind（item2）を実行する必要があります。これにより、これらのそれぞれが属するセットが返されます。その後、アップツリーで表される小さいセットを高いセットに追加する必要があります。検索が発行されたら、常にパスをたどって圧縮します。

パス圧縮を使用してテストされた実装はここにあります。

于 2015-11-10T15:31:26.163 に答える