Union-Find-Datenstruktur erstellen (Python)

Question

Aufgabe:

In dieser Aufgabe soll eine Union-Find-Datenstruktur erstellt werden. Es sei \( V \subset \mathbb{Z}_{\geq 0}^{2} \) eine als Liste von Tupeln \( (x, y) \in \mathbb{Z}_{\geq 0}^{2} \) gegebene endliche Grundmenge.

Klasse Set

Schreiben Sie eine Klasse Set mit dem Attribut

- _elements Liste \( V \) von Tupeln \( (x, y) \in \mathbb{Z}_{\geq 0}^{2} \) und den Methoden

a) __init__(self, V) Initialisiert das Attribut _elements mit der übergebenen Liste \( V \).

b) Elements(self) Gibt Inhalt von_elements als lexikographisch geordnete Liste zurück.

Beispielaufruf:

\( 1>>>\mathrm{S}=\operatorname{Set}([(0,3),(0,1),(1,3),(1,0)]) \)
\( 2>>>\operatorname{print}(\mathrm{S} . \) _elements \( ) \)
\( { }_{3}[(0,3),(0,1),(1,3),(1,0)] \)
\( 4>>> \) S. Elements ( )
\( 5[(0,1),(0,3),(1,0),(1,3)] \)
Klasse Partition

Schreiben Sie eine Klasse Partition mit dem Attribut -Sets (Liste von Set-Objekten) und den Methoden

a) _-init__(self, V) Erzeugt eine Partition von \( V \) in einelementige Mengen, die als SetObjekte in der Liste Sets abgelegt werden. Falls ein Tupel doppelt in der Liste V vorkommt, werfen Sie die Exception 'invalid operation'.

b) __str _self) String-Repräsentation des Partition-Objekts. Gibt eine Liste von Listen als String wieder. Die Teillisten sind die _element-Listen der Set-Objekte in Sets.

Anmerkung: Die Methode wird nicht vom Comajudge abgefragt, sollte aber vorgestellt werden können. Sie dient insbesondere Threr Selbstkontrolle. Dies heiBt auch, dass die SetObjekte in keiner besonderen Reihenfolge ausgedruckt werden müssen.

c) MakeSet (self, \( (x, y)) \) Fügt der Liste Sets ein Set-Objekt hinzu, das mit dem Tupel \( (x, y) \) initialisiert wird. Falls das Tupel \( (x, y) \) bereits in einem Set von Sets enthalten ist, werfen Sie die Exception 'invalid operation'.

d) FindSet(self, \( (x, y)) \) Es sei \( S \) das Set, welches das Tupel \( (x, y) \) enthält. Dann gibt die Methode das Repräsentanten-Tupel S._elements [0] zurück. Falls das Tupel ( \( x, y) \) in keinem Set von Sets enthalten ist, werfen Sie die Exception 'invalid operation'.

e) Union(self, \( (x 1, y 1),(x 2, y 2)) \) Es seien S1 und S2 Set-Objekte in Sets so dass die Repräsentanten S1._elements[0] und S2._elements[0] gleich ( \( \mathrm{x} 1, \mathrm{y} 1) \mathrm{bzw} .(\mathrm{x} 2, \mathrm{y} 2) \) sind. Dann entfernt Union die beiden Objekte S1 und S2 aus Sets und fügt statt ihrer ein neues Objekt S hinzu, das die lexikographisch geordnete Vereinigung von S1 und S2 ist. Insbesondere heißt dies, dass S._elements [0], der Repräsentant des neuen Objekts \( \mathrm{S} \), das lexikographisch kleinere der Tupel ( \( \mathrm{x} 1, \mathrm{y} 1) \) und \( (\mathrm{x} 2, \mathrm{y} 2) \) ist. Falls es keine SetObjekte mit Repräsentanten ( \( x 1, y 1 \) ) oder ( \( x 2 \), y2) gibt, dann werfen Sie die Exception 'invalid operation'. Existieren die Mengen, so sind sie aufgrund der Konstruktion der Klasse disjunkt. Sie müssen diesen Spezialfall also nicht abfangen.

Beispielaufrufe:

\( 1>>>\mathrm{S}= \) Partition \( ([(0,3),(0,1),(1,3),(1,0)]) \)
\( 2>>> \) S. Union \( ((1,3),(0,1)) \)
\( 3>>> \) S. Union \( ((0,3),(0,1)) \)
\( 4>>>\operatorname{print}(S) \)
\( { }_{5}^{5}[[(1,0)],[(0,1),(0,3),(1,3)]] \)
\( 6>>>\mathrm{S} . \) FindSet \( ((1,3)) \)
\( 7(0,1) \)
\( 8>>> \) S. MakeSet \( ((300,1)) \)
\( 9>>> \) S. Union \( ((300,1),(0,1)) \)
\( 10>>>\operatorname{print}(\mathrm{S}) \)
\( { }_{11}[[(1,0)],[(0,1),(0,3),(1,3),(300,1)]] \)
\( 12>>> \) S. FindSet \( ((300,1)) \)
\( 1>>>\mathrm{S}= \) Partition \( ([(0,3),(0,1),(1,3),(1,0)]) \)
\( 2>>> \) S. Union \( ((1,3),(0,1)) \)
\( 3>>> \) S. Union \( ((0,3),(0,1)) \)
\( 4>>> \) print \( (\mathrm{S}) \)
\( 5[[(1,0)],[(0,1),(0,3),(1,3)]] \)
\( 6>>> \) S. FindSet \( ((1,3)) \)
\( 7(0,1) \)
\( 8>>> \) S. MakeSet \( ((300,1)) \)
\( 9>>> \) S. Union \( ((300,1),(0,1)) \)
\( 10>>> \) print \( (\mathrm{S}) \)
\( 11[[(1,0)],[(0,1),(0,3),(1,3),(300,1)]] \)
\( 12>>> \) S. FindSet \( ((300,1)) \)
\( 13(0,1) \)
\( 14>>> \) S. MakeSet \( ((0,0)) \)
\( 15>>> \) S. Union \( ((0,0),(0,1)) \)
\( 16>>> \) S. FindSet \( ((300,1)) \)
\( 17(0,0) \)
\( 18>>> \) print \( (\mathrm{S}) \)
\( 19[[(1,0)],[(0,0),(0,1),(0,3),(1,3),(300,1)]] \)
\( 13(0,1) \)
\( 14>>> \) S. MakeSet \( ((0,0)) \)
\( 15>>> \) S. Union \( ((0,0),(0,1)) \)
\( 16>>> \) S. FindSet \( ((300,1)) \)
\( 17(0,0) \)
\( 18>>>\operatorname{print}(\mathrm{S}) \)
\( 19[[(1,0)],[(0,0),(0,1),(0,3),(1,3),(300,1)]] \)

Answer 1

Antwort mit KI erzeugt

Erstellung der Union-Find-Datenstruktur in Python

Wir erstellen zunächst die Klasse Set, um eine Menge von Tupeln zu repräsentieren, und dann die Klasse Partition, die mehrere Set-Objekte verwaltet.

Klasse Set

python
class Set:
    def __init__(self, V):
        # Initialisiert das Attribut _elements mit der übergebenen Liste V.
        self._elements = V

    def Elements(self):
        # Gibt den Inhalt von _elements als lexikographisch geordnete Liste zurück.
        return sorted(self._elements)

# Beispielaufruf und Tests
S = Set([(0,3),(0,1),(1,3),(1,0)])
print(S._elements)  # Ausgabe: [(0,3),(0,1),(1,3),(1,0)]
print(S.Elements()) # Ausgabe: [(0,1),(0,3),(1,0),(1,3)]

Klasse Partition

python
class Partition:
    def __init__(self, V):
        # Verhindert doppelte Elemente in V
        if len(V) != len(set(V)):
            raise Exception('invalid operation')
        # Erzeugt eine Partition von V in einelementige Mengen
        self.Sets = [Set([item]) for item in V]

    def __str__(self):
        # Gibt eine Liste von Listen als String wieder
        return str([s._elements for s in self.Sets])

    def MakeSet(self, element):
        # Falls das Element bereits in einem Set enthalten ist, wird eine Exception geworfen
        for s in self.Sets:
            if element in s._elements:
                raise Exception('invalid operation')
        # Fügt ein neues Set hinzu
        self.Sets.append(Set([element]))

    def FindSet(self, element):
        # Sucht das Set, das das Element enthält, und gibt dessen Repräsentanten zurück
        for s in self.Sets:
            if element in s._elements:
                return s._elements[0]
        # Falls das Element nicht gefunden wird, wird eine Exception geworfen
        raise Exception('invalid operation')

    def Union(self, element1, element2):
        set1, set2 = None, None
        # Finden der Sets, die element1 und element2 enthalten
        for s in self.Sets:
            if element1 in s._elements:
                set1 = s
            if element2 in s._elements:
                set2 = s
        # Falls eines der Sets nicht gefunden wird, wird eine Exception geworfen
        if set1 is None or set2 is None:
            raise Exception('invalid operation')
        # Entferne set1 und set2 aus der Liste Sets
        self.Sets.remove(set1)
        self.Sets.remove(set2)
        # Erzeuge ein neues Set, das die Vereinigung von set1 und set2 ist
        new_set = sorted(set1._elements + set2._elements)
        self.Sets.append(Set(new_set))

# Beispielaufrufe und Tests
S = Partition([(0,3),(0,1),(1,3),(1,0)])
S.Union((1,3),(0,1))
S.Union((0,3),(0,1))
print(S)             # Ausgabe: [[(1,0)], [(0,1), (0,3), (1,3)]]
print(S.FindSet((1,3))) # Ausgabe: (0,1)
S.MakeSet((300,1))
S.Union((300,1),(0,1))
print(S)             # Ausgabe: [[(1,0)], [(0,1), (0,3), (1,3), (300,1)]]
print(S.FindSet((300,1))) # Ausgabe: (0,1)
S.MakeSet((0,0))
S.Union((0,0),(0,1))
print(S.FindSet((300,1))) # Ausgabe: (0,0)
print(S)             # Ausgabe: [[(1,0)], [(0,0), (0,1), (0,3), (1,3), (300,1)]]

In diesem Code haben wir zwei Klassen erstellt: Set und Partition. Jede Klasse hat ihre spezifische Funktionalität und Methoden wie beschrieben. Dies ermöglicht eine effiziente Verwaltung und Manipulation von Mengen und deren Partitionen in Python.