0 Daumen
72 Aufrufe

Frage:

Aufgabenstellung
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)]] \)


Hey ich bin bei Programieren echt schlecht und muss diese Aufgabe losen hat wer eine Idee wie ich es machen kann

von

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community