Nächste Seite: Re: Jetzt neu Uebung Aufwärts: Graphen, Schaltwerke und Zahlen Vorherige Seite: Jetzt neu Uebung
adj_list = [[3,2,6,5],[4,10,5,1],[1,4,15,10,8,9],[3,2,10,7],[1,2,9,11],[1,8,14,11],[4,12],[6,3],[5,3,14,16],[3,4,13,15,12,2],[6,14,16,5],[7,13,10,16],[12,10,16,14],[11,9,13,6],[3,10],[11,12,9,13]]
# also, ich habe jetzt erst mal diesen Eulergraphen von mir genommen und in eine Adjanzenzliste fuer Python 3 umgewandelt. Der Nachteil. Python faengt bei 0 an zu zaehlen, bei den Knoten V Vertices habe ich bei 1 angefangen. Das loese ich mit Python, ich erzeuge eine Kopie der Liste und subtrahiere in der Kopie von jedem Zustand, die Zahl 1.
# Mit len fuer jede Liste in der Liste ist das kein Problem auch, wenn die Listen innerhalb unterschiedliche Laengen haben, 2, 4, und 6
# Nachher wird der Algorithmus einfach so aussehen, angefangen bei einem Zustand gehe ich immer weiter, immer weiter bis ich am Ausgangsknoten angekommen bin, dabei entferne ich, das in Python eben ganz einfach moeglich, sowohl u und v einer Kante (u,v) und zwar das v bei u und das u bei v. Nichts ist in Python einfacher als das. Da es ein Eulergraph ist, muss ich wohl oder uebel irgendwann wieder am Ausgangsknoten ankommen, was vollkommen legitim ist, auch mit nur einem Kreis habe ich mein Ziel erreicht, habe ich allerdings - bzw. mein Programm so gewaehlt, dass ich nicht die ganze List leer habe, wenn ich wieder da bin, dann sehe ich die Liste ist nicht leer und beginne diese Ebenso zu bearbeiten
# im letzten Schritt, kopiere ich alle Listen der Reihe nach ineinander an die entsprechenden Knoten, was in Python kein Problem ist
# und im allerletzten Schritt, mache ich aus dieser Schachtelung von Listen eine einzige
also, ich habe jetzt erst mal diesen Eulergraphen von mir genommen und in eine Adjanzenzliste fuer Python 3 umgewandelt. Der Nachteil. Python faengt bei 0 an zu zaehlen, bei den Knoten V Vertices habe ich bei 1 angefangen. Das loese ich mit Python, ich erzeuge eine Kopie der Liste und subtrahiere in der Kopie von jedem Zustand, die Zahl 1.
Mit len fuer jede Liste in der Liste ist das kein Problem auch, wenn die Listen innerhalb unterschiedliche Laengen haben, 2, 4, und 6
Nachher wird der Algorithmus einfach so aussehen, angefangen bei einem Zustand gehe ich immer weiter, immer weiter bis ich am Ausgangsknoten angekommen bin, dabei entferne ich, das in Python eben ganz einfach moeglich, sowohl u und v einer Kante (u,v) und zwar das v bei u und das u bei v. Nichts ist in Python einfacher als das. Da es ein Eulergraph ist, muss ich wohl oder uebel irgendwann wieder am Ausgangsknoten ankommen, was vollkommen legitim ist, auch mit nur einem Kreis habe ich mein Ziel erreicht, habe ich allerdings - bzw. mein Programm so gewaehlt, dass ich nicht die ganze List leer habe, wenn ich wieder da bin, dann sehe ich die Liste ist nicht leer und beginne diese Ebenso zu bearbeiten
im letzten Schritt, kopiere ich alle Listen der Reihe nach ineinander an die entsprechenden Knoten, was in Python kein Problem ist
und im allerletzten Schritt, mache ich aus dieser Schachtelung von Listen eine einzige
Das sieht doch schon mal gut aus
adj_lst = [[3,2,6,5],[4,10,5,1],[1,4,15,10,8,9],[3,2,10,7],[1,2,9,11],[1,8,14,11],[4,12],[6,3],[5,3,14,16],[3,4,13,15,12,2],[6,14,16,5],[7,13,10,16],[12,10,16,14],[11,9,13,6],[3,10],[11,12,9,13]]
# also, ich habe jetzt erst mal diesen Eulergraphen von mir genommen und in eine Adjanzenzliste fuer Python 3 umgewandelt. Der Nachteil. Python faengt bei 0 an zu zaehlen, bei den Knoten V Vertices habe ich bei 1 angefangen. Das loese ich mit Python, ich erzeuge eine Kopie der Liste und subtrahiere in der Kopie von jedem Zustand, die Zahl 1.
# Mit len fuer jede Liste in der Liste ist das kein Problem auch, wenn die Listen innerhalb unterschiedliche Laengen haben, 2, 4, und 6
# Nachher wird der Algorithmus einfach so aussehen, angefangen bei einem Zustand gehe ich immer weiter, immer weiter bis ich am Ausgangsknoten angekommen bin, dabei entferne ich, das in Python eben ganz einfach moeglich, sowohl u und v einer Kante (u,v) und zwar das v bei u und das u bei v. Nichts ist in Python einfacher als das. Da es ein Eulergraph ist, muss ich wohl oder uebel irgendwann wieder am Ausgangsknoten ankommen, was vollkommen legitim ist, auch mit nur einem Kreis habe ich mein Ziel erreicht, habe ich allerdings - bzw. mein Programm so gewaehlt, dass ich nicht die ganze List leer habe, wenn ich wieder da bin, dann sehe ich die Liste ist nicht leer und beginne diese Ebenso zu bearbeiten
# im letzten Schritt, kopiere ich alle Listen der Reihe nach ineinander an die entsprechenden Knoten, was in Python kein Problem ist
# und im allerletzten Schritt, mache ich aus dieser Schachtelung von Listen eine einzige
import copy
a = copy.deepcopy (adj_lst)
print (adj_lst)
print (a)
i = 0
while i < len (a):
j = 0
while j < len (a[i]):
a [i][j] = a [i][j] - 1
j = j + 1
i = i + 1
print (a)
david@laptop-peaq:~\$ python3 euler20240805.py [[3, 2, 6, 5], [4, 10, 5, 1], [1, 4, 15, 10, 8, 9], [3, 2, 10, 7], [1, 2, 9, 11], [1, 8, 14, 11], [4, 12], [6, 3], [5, 3, 14, 16], [3, 4, 13, 15, 12, 2], [6, 14, 16, 5], [7, 13, 10, 16], [12, 10, 16, 14], [11, 9, 13, 6], [3, 10], [11, 12, 9, 13]] [[3, 2, 6, 5], [4, 10, 5, 1], [1, 4, 15, 10, 8, 9], [3, 2, 10, 7], [1, 2, 9, 11], [1, 8, 14, 11], [4, 12], [6, 3], [5, 3, 14, 16], [3, 4, 13, 15, 12, 2], [6, 14, 16, 5], [7, 13, 10, 16], [12, 10, 16, 14], [11, 9, 13, 6], [3, 10], [11, 12, 9, 13]] [[2, 1, 5, 4], [3, 9, 4, 0], [0, 3, 14, 9, 7, 8], [2, 1, 9, 6], [0, 1, 8, 10], [0, 7, 13, 10], [3, 11], [5, 2], [4, 2, 13, 15], [2, 3, 12, 14, 11, 1], [5, 13, 15, 4], [6, 12, 9, 15], [11, 9, 15, 13], [10, 8, 12, 5], [2, 9], [10, 11, 8, 12]] david@laptop-peaq:~\$
So, jetzt probiere ich es probehalber mit dem ersten Kreis, ich fange bei irgendeinem knoten an
Dabei merke ich mir zunaechst die Knoten in einem weiteren Feld, wo ich sie anhaenge mit
lst.append ()
Den Knoten u und v, die beiden Nachbarn der Kante entferne ich jeweils mit
a [v].remove (u) a [u].remove (v)
remove entfernt auf jeden Fall den entsprechenden Knoten, da allerdings parallele Kanten nicht erlaubt sind, taucht er in jedem Knoten nur ein Mal auf, darum muss man sich keine Sorgen machen
Das sieht doch schon mal gut aus
adj_lst = [[3,2,6,5],[4,10,5,1],[1,4,15,10,8,9],[3,2,10,7],[1,2,9,11],[1,8,14,11],[4,12],[6,3],[5,3,14,16],[3,4,13,15,12,2],[6,14,16,5],[7,13,10,16],[12,10,16,14],[11,9,13,6],[3,10],[11,12,9,13]]
# also, ich habe jetzt erst mal diesen Eulergraphen von mir genommen und in eine Adjanzenzliste fuer Python 3 umgewandelt. Der Nachteil. Python faengt bei 0 an zu zaehlen, bei den Knoten V Vertices habe ich bei 1 angefangen. Das loese ich mit Python, ich erzeuge eine Kopie der Liste und subtrahiere in der Kopie von jedem Zustand, die Zahl 1.
# Mit len fuer jede Liste in der Liste ist das kein Problem auch, wenn die Listen innerhalb unterschiedliche Laengen haben, 2, 4, und 6
# Nachher wird der Algorithmus einfach so aussehen, angefangen bei einem Zustand gehe ich immer weiter, immer weiter bis ich am Ausgangsknoten angekommen bin, dabei entferne ich, das in Python eben ganz einfach moeglich, sowohl u und v einer Kante (u,v) und zwar das v bei u und das u bei v. Nichts ist in Python einfacher als das. Da es ein Eulergraph ist, muss ich wohl oder uebel irgendwann wieder am Ausgangsknoten ankommen, was vollkommen legitim ist, auch mit nur einem Kreis habe ich mein Ziel erreicht, habe ich allerdings - bzw. mein Programm so gewaehlt, dass ich nicht die ganze List leer habe, wenn ich wieder da bin, dann sehe ich die Liste ist nicht leer und beginne diese Ebenso zu bearbeiten
# im letzten Schritt, kopiere ich alle Listen der Reihe nach ineinander an die entsprechenden Knoten, was in Python kein Problem ist
# und im allerletzten Schritt, mache ich aus dieser Schachtelung von Listen eine einzige
import copy
a = copy.deepcopy (adj_lst)
print (adj_lst)
print (a)
i = 0
while i < len (a):
j = 0
while j < len (a[i]):
a [i][j] = a [i][j] - 1
j = j + 1
i = i + 1
print (a)
euler = []
v0 = 0
v = v0
u = a [v][0]
euler.append (v)
while u != v0:
print (u)
euler.append (u)
a [u].remove (v)
a [v].remove (u)
v = u
u = a [u][0]
euler.append (u)
print (euler)
david@laptop-peaq:~\$ python3 euler20240805.py [[3, 2, 6, 5], [4, 10, 5, 1], [1, 4, 15, 10, 8, 9], [3, 2, 10, 7], [1, 2, 9, 11], [1, 8, 14, 11], [4, 12], [6, 3], [5, 3, 14, 16], [3, 4, 13, 15, 12, 2], [6, 14, 16, 5], [7, 13, 10, 16], [12, 10, 16, 14], [11, 9, 13, 6], [3, 10], [11, 12, 9, 13]] [[3, 2, 6, 5], [4, 10, 5, 1], [1, 4, 15, 10, 8, 9], [3, 2, 10, 7], [1, 2, 9, 11], [1, 8, 14, 11], [4, 12], [6, 3], [5, 3, 14, 16], [3, 4, 13, 15, 12, 2], [6, 14, 16, 5], [7, 13, 10, 16], [12, 10, 16, 14], [11, 9, 13, 6], [3, 10], [11, 12, 9, 13]] [[2, 1, 5, 4], [3, 9, 4, 0], [0, 3, 14, 9, 7, 8], [2, 1, 9, 6], [0, 1, 8, 10], [0, 7, 13, 10], [3, 11], [5, 2], [4, 2, 13, 15], [2, 3, 12, 14, 11, 1], [5, 13, 15, 4], [6, 12, 9, 15], [11, 9, 15, 13], [10, 8, 12, 5], [2, 9], [10, 11, 8, 12]] 2 3 1 9 2 14 9 3 6 11 12 9 11 15 10 5 [0, 2, 3, 1, 9, 2, 14, 9, 3, 6, 11, 12, 9, 11, 15, 10, 5, 0] david@laptop-peaq:~\$
[0, 2, 3, 1, 9, 2, 14, 9, 3, 6, 11, 12, 9, 11, 15, 10, 5, 0] # im naechsten schritt pruefen wir nach ob dieser Kreis in unserem Graphen tatsaechlich einen Kreis ergib
Wir kontrollieren danach ebenso ob er die Kanten richtig entfernt hat und wir addieren jetzt in eine Kopie des ersten Euler Teilkreises noch mal ueberall eine 1
david@laptop-peaq:~\$ python3 euler20240805.py [[3, 2, 6, 5], [4, 10, 5, 1], [1, 4, 15, 10, 8, 9], [3, 2, 10, 7], [1, 2, 9, 11], [1, 8, 14, 11], [4, 12], [6, 3], [5, 3, 14, 16], [3, 4, 13, 15, 12, 2], [6, 14, 16, 5], [7, 13, 10, 16], [12, 10, 16, 14], [11, 9, 13, 6], [3, 10], [11, 12, 9, 13]] [[3, 2, 6, 5], [4, 10, 5, 1], [1, 4, 15, 10, 8, 9], [3, 2, 10, 7], [1, 2, 9, 11], [1, 8, 14, 11], [4, 12], [6, 3], [5, 3, 14, 16], [3, 4, 13, 15, 12, 2], [6, 14, 16, 5], [7, 13, 10, 16], [12, 10, 16, 14], [11, 9, 13, 6], [3, 10], [11, 12, 9, 13]] [[2, 1, 5, 4], [3, 9, 4, 0], [0, 3, 14, 9, 7, 8], [2, 1, 9, 6], [0, 1, 8, 10], [0, 7, 13, 10], [3, 11], [5, 2], [4, 2, 13, 15], [2, 3, 12, 14, 11, 1], [5, 13, 15, 4], [6, 12, 9, 15], [11, 9, 15, 13], [10, 8, 12, 5], [2, 9], [10, 11, 8, 12]] 2 3 1 9 2 14 9 3 6 11 12 9 11 15 10 5 [0, 2, 3, 1, 9, 2, 14, 9, 3, 6, 11, 12, 9, 11, 15, 10, 5, 0] [1, 3, 4, 2, 10, 3, 15, 10, 4, 7, 12, 13, 10, 12, 16, 11, 6, 1] david@laptop-peaq:~\$
Jetzt gucke ich ob die neue Adjanzensliste stimmt, dann pause
Die stimmt generell ein kleiner Fehler ist drin - natuerlich und das ist das wichtigste, in jedem Knoten fuehren immer eine gleiche Anzahl an Kanten rein und raus - also die Valenz eines Knotens ist gerade. Das ist logisch, solange sie gerade ist, kann ich so oft rein wie raus
Gut, aber Schleifen Programmieren hat das manchmal an sich, schaut man hier an alle Knoten stimmt es, das sagt auch unser Erstes Ergebnis, nur leider wurde, am Anfang der erste Nachbarknoten im ersten Knoten nicht entfernt
david@laptop-peaq:~\$ python3 euler20240805.py [[3, 2, 6, 5], [4, 10, 5, 1], [1, 4, 15, 10, 8, 9], [3, 2, 10, 7], [1, 2, 9, 11], [1, 8, 14, 11], [4, 12], [6, 3], [5, 3, 14, 16], [3, 4, 13, 15, 12, 2], [6, 14, 16, 5], [7, 13, 10, 16], [12, 10, 16, 14], [11, 9, 13, 6], [3, 10], [11, 12, 9, 13]] [[3, 2, 6, 5], [4, 10, 5, 1], [1, 4, 15, 10, 8, 9], [3, 2, 10, 7], [1, 2, 9, 11], [1, 8, 14, 11], [4, 12], [6, 3], [5, 3, 14, 16], [3, 4, 13, 15, 12, 2], [6, 14, 16, 5], [7, 13, 10, 16], [12, 10, 16, 14], [11, 9, 13, 6], [3, 10], [11, 12, 9, 13]] [[2, 1, 5, 4], [3, 9, 4, 0], [0, 3, 14, 9, 7, 8], [2, 1, 9, 6], [0, 1, 8, 10], [0, 7, 13, 10], [3, 11], [5, 2], [4, 2, 13, 15], [2, 3, 12, 14, 11, 1], [5, 13, 15, 4], [6, 12, 9, 15], [11, 9, 15, 13], [10, 8, 12, 5], [2, 9], [10, 11, 8, 12]] 2 3 1 9 2 14 9 3 6 11 12 9 11 15 10 5 [0, 2, 3, 1, 9, 2, 14, 9, 3, 6, 11, 12, 9, 11, 15, 10, 5, 0] [1, 3, 4, 2, 10, 3, 15, 10, 4, 7, 12, 13, 10, 12, 16, 11, 6, 1] [[1, 5, 4], [4, 0], [7, 8], [], [0, 1, 8, 10], [0, 7, 13], [], [5, 2], [4, 2, 13, 15], [], [13, 4], [], [15, 13], [10, 8, 12, 5], [], [8, 12]] david@laptop-peaq:~\$
Wenn das Problem behoben ist, was schneller getan ist, als gesagt, dann wuerde es sich lohnen nach einer Python Funktion fuer listen zu suchen, die alle Elemente, die leere Listen sind entfernt
Das ist wahrscheinlich nicht der erste Knoten sondern der letzte, das Problem ist nicht der Beginn der Schleife sondern das ende, das ist logisch, weil die Operation zum entfernen des Knotens wird durch den Abbruch nicht mehr ausgefuehrt
Nein, fehler, fehler, fehler!
Keine leeren Liste entfernen, das fuehrt in die Katastrophe, denn die Knoten sind durchnummeriert
0, 1, 2, 3, ...
und steht da eine leere Liste
[]
[[1, 5, 4], [4, 0], [7, 8], [], [0, 1, 8, 10], [0, 7, 13], [], [5, 2], [4, 2, 13, 15], [], [13, 4], [], [15, 13], [10, 8, 12, 5], [], [8, 12]]
Ich fand bei dem ersten Knoten (0) die 6 (5) genau das ist er. Und bei 6 (5) fand ich 1 (0)
Also ist es das Schleifen ende und wir muessen den Code machen
euler = []
v0 = 0
v = v0
u = a [v][0]
euler.append (v)
while u != v0:
print (u)
euler.append (u)
a [u].remove (v)
a [v].remove (u)
v = u
u = a [u][0]
a [u].remove (v)
a [v].remove (u)
und siehe da es funktioniert
david@laptop-peaq:~\$ python3 euler20240805b.py [[3, 2, 6, 5], [4, 10, 5, 1], [1, 4, 15, 10, 8, 9], [3, 2, 10, 7], [1, 2, 9, 11], [1, 8, 14, 11], [4, 12], [6, 3], [5, 3, 14, 16], [3, 4, 13, 15, 12, 2], [6, 14, 16, 5], [7, 13, 10, 16], [12, 10, 16, 14], [11, 9, 13, 6], [3, 10], [11, 12, 9, 13]] [[3, 2, 6, 5], [4, 10, 5, 1], [1, 4, 15, 10, 8, 9], [3, 2, 10, 7], [1, 2, 9, 11], [1, 8, 14, 11], [4, 12], [6, 3], [5, 3, 14, 16], [3, 4, 13, 15, 12, 2], [6, 14, 16, 5], [7, 13, 10, 16], [12, 10, 16, 14], [11, 9, 13, 6], [3, 10], [11, 12, 9, 13]] [[2, 1, 5, 4], [3, 9, 4, 0], [0, 3, 14, 9, 7, 8], [2, 1, 9, 6], [0, 1, 8, 10], [0, 7, 13, 10], [3, 11], [5, 2], [4, 2, 13, 15], [2, 3, 12, 14, 11, 1], [5, 13, 15, 4], [6, 12, 9, 15], [11, 9, 15, 13], [10, 8, 12, 5], [2, 9], [10, 11, 8, 12]] 2 3 1 9 2 14 9 3 6 11 12 9 11 15 10 5 [0, 2, 3, 1, 9, 2, 14, 9, 3, 6, 11, 12, 9, 11, 15, 10, 5, 0] [1, 3, 4, 2, 10, 3, 15, 10, 4, 7, 12, 13, 10, 12, 16, 11, 6, 1] [[1, 4], [4, 0], [7, 8], [], [0, 1, 8, 10], [7, 13], [], [5, 2], [4, 2, 13, 15], [], [13, 4], [], [15, 13], [10, 8, 12, 5], [], [8, 12]] david@laptop-peaq:~\$
So, im naechsten schritt, tun wir in einer weiteren Liste, den Anfangsknoten speichern und in einer wieder weiteren Liste, die Liste die gerade eben erstellt wurde
Dann gehen wir die Adjanzensliste durch und wiederholen den Vorgang, solange bis sie leer ist
# das sieht schon mal gut aus
adj_lst = [[3,2,6,5],[4,10,5,1],[1,4,15,10,8,9],[3,2,10,7],[1,2,9,11],[1,8,14,11],[4,12],[6,3],[5,3,14,16],[3,4,13,15,12,2],[6,14,16,5],[7,13,10,16],[12,10,16,14],[11,9,13,6],[3,10],[11,12,9,13]]
# also, ich habe jetzt erst mal diesen Eulergraphen von mir genommen und in eine Adjanzenzliste fuer Python 3 umgewandelt. Der Nachteil. Python faengt bei 0 an zu zaehlen, bei den Knoten V Vertices habe ich bei 1 angefangen. Das loese ich mit Python, ich erzeuge eine Kopie der Liste und subtrahiere in der Kopie von jedem Zustand, die Zahl 1.
# Mit len fuer jede Liste in der Liste ist das kein Problem auch, wenn die Listen innerhalb unterschiedliche Laengen haben, 2, 4, und 6
# Nachher wird der Algorithmus einfach so aussehen, angefangen bei einem Zustand gehe ich immer weiter, immer weiter bis ich am Ausgangsknoten angekommen bin, dabei entferne ich, das in Python eben ganz einfach moeglich, sowohl u und v einer Kante (u,v) und zwar das v bei u und das u bei v. Nichts ist in Python einfacher als das. Da es ein Eulergraph ist, muss ich wohl oder uebel irgendwann wieder am Ausgangsknoten ankommen, was vollkommen legitim ist, auch mit nur einem Kreis habe ich mein Ziel erreicht, habe ich allerdings - bzw. mein Programm so gewaehlt, dass ich nicht die ganze List leer habe, wenn ich wieder da bin, dann sehe ich die Liste ist nicht leer und beginne diese Ebenso zu bearbeiten
# im letzten Schritt, kopiere ich alle Listen der Reihe nach ineinander an die entsprechenden Knoten, was in Python kein Problem ist
# und im allerletzten Schritt, mache ich aus dieser Schachtelung von Listen eine einzige
import copy
a = copy.deepcopy (adj_lst)
print (adj_lst)
print (a)
i = 0
while i < len (a):
j = 0
while j < len (a[i]):
a [i][j] = a [i][j] - 1
j = j + 1
i = i + 1
print (a)
flag = False
start_v = []
circles = []
while flag == False:
euler = []
v0 = 0
while (v0 < len (a)) and not a[v0]:
v0 = v0 + 1
if v0 < len (a):
start_v.append (v0)
v = v0
u = a [v][0]
euler.append (v)
start_v = []
while u != v0:
print (u)
euler.append (u)
a [u].remove (v)
a [v].remove (u)
v = u
u = a [u][0]
a [u].remove (v)
a [v].remove (u)
euler.append (u)
print (euler)
print (a)
circles.append (euler)
else:
flag = True
print ("----")
print (start_v)
print (circles)
euler_prnt = copy.deepcopy (euler)
# Das sieht schon mal gut aus - das Ergebnis david@laptop-peaq:~\$ python3 euler20240805c.py [[3, 2, 6, 5], [4, 10, 5, 1], [1, 4, 15, 10, 8, 9], [3, 2, 10, 7], [1, 2, 9, 11], [1, 8, 14, 11], [4, 12], [6, 3], [5, 3, 14, 16], [3, 4, 13, 15, 12, 2], [6, 14, 16, 5], [7, 13, 10, 16], [12, 10, 16, 14], [11, 9, 13, 6], [3, 10], [11, 12, 9, 13]] [[3, 2, 6, 5], [4, 10, 5, 1], [1, 4, 15, 10, 8, 9], [3, 2, 10, 7], [1, 2, 9, 11], [1, 8, 14, 11], [4, 12], [6, 3], [5, 3, 14, 16], [3, 4, 13, 15, 12, 2], [6, 14, 16, 5], [7, 13, 10, 16], [12, 10, 16, 14], [11, 9, 13, 6], [3, 10], [11, 12, 9, 13]] [[2, 1, 5, 4], [3, 9, 4, 0], [0, 3, 14, 9, 7, 8], [2, 1, 9, 6], [0, 1, 8, 10], [0, 7, 13, 10], [3, 11], [5, 2], [4, 2, 13, 15], [2, 3, 12, 14, 11, 1], [5, 13, 15, 4], [6, 12, 9, 15], [11, 9, 15, 13], [10, 8, 12, 5], [2, 9], [10, 11, 8, 12]] 2 3 1 9 2 14 9 3 6 11 12 9 11 15 10 5 [0, 2, 3, 1, 9, 2, 14, 9, 3, 6, 11, 12, 9, 11, 15, 10, 5, 0] [[1, 4], [4, 0], [7, 8], [], [0, 1, 8, 10], [7, 13], [], [5, 2], [4, 2, 13, 15], [], [13, 4], [], [15, 13], [10, 8, 12, 5], [], [8, 12]] 1 4 [0, 1, 4, 0] [[], [], [7, 8], [], [8, 10], [7, 13], [], [5, 2], [4, 2, 13, 15], [], [13, 4], [], [15, 13], [10, 8, 12, 5], [], [8, 12]] 7 5 13 10 4 8 [2, 7, 5, 13, 10, 4, 8, 2] [[], [], [], [], [], [], [], [], [13, 15], [], [], [], [15, 13], [8, 12], [], [8, 12]] 13 12 15 [8, 13, 12, 15, 8] [[], [], [], [], [], [], [], [], [], [], [], [], [], [], [], []] ---- [] [[0, 2, 3, 1, 9, 2, 14, 9, 3, 6, 11, 12, 9, 11, 15, 10, 5, 0], [0, 1, 4, 0], [2, 7, 5, 13, 10, 4, 8, 2], [8, 13, 12, 15, 8]] david@laptop-peaq:~\$
[0, 2, 3, 1, 9, 2, 14, 9, 3, 6, 11, 12, 9, 11, 15, 10, 5, 0] [0, 1, 4, 0] [2, 7, 5, 13, 10, 4, 8, 2] [8, 13, 12, 15, 8]
Jetzt besteht die Kunst im 2. Schritt darin, die einzelnen Kreise ineinander ein zu setzen, ich gehe einfach die gesamten anderen Kreise durch, ich suche in den anderen Kreisen nach dem Knoten mit dem entsprechenden Anfangsknoten des Kreises der eingesetzt wird, dann entferne ich den Eintrag des gesamtes Kreises der eingesetzt wird, aus der Liste und wo ich den Kreis einsetze entferne ich noch den Knoten, wo eingesetzt wird.
Einsetzen, laesst sich doch wohl nur rekursiv loesen, weil es koennen theoretisch beliebig viele Ringe in einem beliebig vielen Ring sitzen und das mit schleifen zu machen hoffnungslos sei denn man geht immer tiefer in des die Liste also das Feld, in dem man sozusagen dieses Feld, wo man das eingesetzt hat, zusammen mit den eingesetzten als einfaellt begreift, dann muesste man aber sozusagen das Feld gleich aufloesen also man kann das wo man das einsetzt wenn da schon Feld drin sitzt und da wieder was reinsetzen es faellt im Feld dann koennte man das aeussere als einfaellt begreifen dann muesste man das nicht rekursiv machen dann muesste man das Feld, aber was drin sitzt schon bereits aufgeloest haben. Anders geht's nicht, weil selbst wenn ich das Alsfeld begreife und es sind trotzdem Wiederfelder im Feld das ist ein Feld im Veldenlist in der Liste und die hatten eigenen Index. Die Liste in der Liste hat wieder einen eigenen Index und dann so unendlich viele werden koennen sind die Schachteln in die C sozusagen gehen gegen unendlich und da gibt's keine normale Grenze und nicht nur das ist die Grenze nicht gibt, das laesst sich nicht anders loesen als rekursiv. Aber jetzt muss ich kurz Pause machen. Ich brauch Kurzpause Nix uebers Knie brechen.
Nein, das einfachste ist es ohne Rekursion das zu machen weil man muss nur ne Extra Funktion schreiben die wird immer ueber das Feld aufgeloest wenn Felder im Feld stecken und nicht mehr und dann wird das Feld was im Feld steckt wenn's eins drin steckt. Das kann man mit halb abfragen und der Laenge des Feldes fast drin steckt fuer jedes Element im aeusseren fehlt wenn es der Fall ist dann nimmt man jedes einzelne Element raus haengt vor des Feld im aeusseren Feld an und nimmt im Inneren Feld raus das Element, bis das Innere Feld leer ist und dann entfernt entfernt man das Innere Feld das ist wohl das einfachste, aber ich brauch kurz Pause.
# ich habe die Loesung fuer das Verschmelzen des Feldes gefunden, ich finde sie sehr elegant
# test
b = [1,2,3,[4,5,6],7,8,9]
if type (b) == list:
print ("yeah!")
if type (b [0]) == list:
print ("yeah!")
else:
print ("no!")
i = 0
while i < len (b):
print (b [i])
if type (b [i]) == list:
if len (b [i]) > 0:
b [i].reverse ()
x = b[i].pop ()
b [i].reverse ()
b.insert (i,x)
# b [i] = x
i = i + 1
b.remove ([])
print (b)
yeah! no! 1 2 3 [4, 5, 6] [5, 6] [6] [] 7 8 9 [1, 2, 3, 4, 5, 6, 7, 8, 9] david@laptop-peaq:~\$
Jetzt Gehstueck fuer Stueck die Listen durch, wenn ich den Anfang dann der List einmal in der naechsten Liste habe sozusagen in der naechsten Liste. Dann suche ich den Anfang in jeder anderen Liste und in der ersten, in der ich ihn gefunden hab jetzt rein und mach das wie gerade eben, dass es dann zu einer Liste verschmilzt.
# Ich habe es schon fast geschafft, das ist das Ergebnis [0, 1, 4, 0, 2, 7, 5, 13, 10, 4, 8, 13, 12, 15, 8, 2, 3, 1, 9, 2, 14, 9, 3, 6, 11, 12, 9, 11, 15, 10, 5, 0]
Allerdings gibt es danach erst noch eine Fehlermeldung
Ok, es ist gelungen, ich habe noch mal etwas ganz geaendert, noch mal ganz anders gemacht, jetzt geht es 100
[[0, 2, 3, 1, 9, 2, 14, 9, 3, 6, 11, 12, 9, 11, 15, 10, 5, 0], [0, 1, 4, 0], [2, 7, 5, 13, 10, 4, 8, 2], [8, 13, 12, 15, 8]] [[0, 1, 4, 0, 2, 7, 5, 13, 10, 4, 8, 13, 12, 15, 8, 2, 3, 1, 9, 2, 14, 9, 3, 6, 11, 12, 9, 11, 15, 10, 5, 0]] david@laptop-peaq:~\$
while j < len (circles [0]):
i = 1
while i < len (circles):
if circles [0][j] == circles [i][0]:
circles [0][j] = circles [i]
merge (circles [0])
circles.remove (circles [i])
i = i + 1
j = j + 1
print (circles)
adj_lst = [[3,2,6,5],[4,10,5,1],[1,4,15,10,8,9],[3,2,10,7],[1,2,9,11],[1,8,14,11],[4,12],[6,3],[5,3,14,16],[3,4,13,15,12,2],[6,14,16,5],[7,13,10,16],[12,10,16,14],[11,9,13,6],[3,10],[11,12,9,13]]
# also, ich habe jetzt erst mal diesen Eulergraphen von mir genommen und in eine Adjanzenzliste fuer Python 3 umgewandelt. Der Nachteil. Python faengt bei 0 an zu zaehlen, bei den Knoten V Vertices habe ich bei 1 angefangen. Das loese ich mit Python, ich erzeuge eine Kopie der Liste und subtrahiere in der Kopie von jedem Zustand, die Zahl 1.
# Mit len fuer jede Liste in der Liste ist das kein Problem auch, wenn die Listen innerhalb unterschiedliche Laengen haben, 2, 4, und 6
# Nachher wird der Algorithmus einfach so aussehen, angefangen bei einem Zustand gehe ich immer weiter, immer weiter bis ich am Ausgangsknoten angekommen bin, dabei entferne ich, das in Python eben ganz einfach moeglich, sowohl u und v einer Kante (u,v) und zwar das v bei u und das u bei v. Nichts ist in Python einfacher als das. Da es ein Eulergraph ist, muss ich wohl oder uebel irgendwann wieder am Ausgangsknoten ankommen, was vollkommen legitim ist, auch mit nur einem Kreis habe ich mein Ziel erreicht, habe ich allerdings - bzw. mein Programm so gewaehlt, dass ich nicht die ganze List leer habe, wenn ich wieder da bin, dann sehe ich die Liste ist nicht leer und beginne diese Ebenso zu bearbeiten
# im letzten Schritt, kopiere ich alle Listen der Reihe nach ineinander an die entsprechenden Knoten, was in Python kein Problem ist
# und im allerletzten Schritt, mache ich aus dieser Schachtelung von Listen eine einzige
import copy
a = copy.deepcopy (adj_lst)
print (adj_lst)
print (a)
i = 0
while i < len (a):
j = 0
while j < len (a[i]):
a [i][j] = a [i][j] - 1
j = j + 1
i = i + 1
print (a)
flag = False
start_v = []
circles = []
while flag == False:
euler = []
v0 = 0
while (v0 < len (a)) and not a[v0]:
v0 = v0 + 1
if v0 < len (a):
start_v.append (v0)
v = v0
u = a [v][0]
euler.append (v)
start_v = []
while u != v0:
print (u)
euler.append (u)
a [u].remove (v)
a [v].remove (u)
v = u
u = a [u][0]
a [u].remove (v)
a [v].remove (u)
euler.append (u)
print (euler)
print (a)
circles.append (euler)
else:
flag = True
print ("----")
print (start_v)
print (circles)
# test
b = [1,2,3,[4,5,6],7,8,9]
if type (b) == list:
print ("yeah!")
if type (b [0]) == list:
print ("yeah!")
else:
print ("no!")
def merge (b):
i = 0
while i < len (b):
#print (b [i])
if type (b [i]) == list:
if len (b [i]) > 0:
b [i].reverse ()
x = b[i].pop ()
b [i].reverse ()
b.insert (i,x)
# b [i] = x
i = i + 1
b.remove ([])
return b
merge (b)
print (b)
print (circles)
j = 0
while j < len (circles [0]):
i = 1
while i < len (circles):
if circles [0][j] == circles [i][0]:
circles [0][j] = circles [i]
merge (circles [0])
circles.remove (circles [i])
i = i + 1
j = j + 1
print (circles)
war am Ende einfacher als erst gemacht
[[0, 2, 3, 1, 9, 2, 14, 9, 3, 6, 11, 12, 9, 11, 15, 10, 5, 0], [0, 1, 4, 0], [2, 7, 5, 13, 10, 4, 8, 2], [8, 13, 12, 15, 8]] [[0, 1, 4, 0, 2, 7, 5, 13, 10, 4, 8, 13, 12, 15, 8, 2, 3, 1, 9, 2, 14, 9, 3, 6, 11, 12, 9, 11, 15, 10, 5, 0]]
[[3, 2, 6, 5], [4, 10, 5, 1], [1, 4, 15, 10, 8, 9], [3, 2, 10, 7], [1, 2, 9, 11], [1, 8, 14, 11], [4, 12], [6, 3], [5, 3, 14, 16], [3, 4, 13, 15, 12, 2], [6, 14, 16, 5], [7, 13, 10, 16], [12, 10, 16, 14], [11, 9, 13, 6], [3, 10], [11, 12, 9, 13]] [[3, 2, 6, 5], [4, 10, 5, 1], [1, 4, 15, 10, 8, 9], [3, 2, 10, 7], [1, 2, 9, 11], [1, 8, 14, 11], [4, 12], [6, 3], [5, 3, 14, 16], [3, 4, 13, 15, 12, 2], [6, 14, 16, 5], [7, 13, 10, 16], [12, 10, 16, 14], [11, 9, 13, 6], [3, 10], [11, 12, 9, 13]] [[2, 1, 5, 4], [3, 9, 4, 0], [0, 3, 14, 9, 7, 8], [2, 1, 9, 6], [0, 1, 8, 10], [0, 7, 13, 10], [3, 11], [5, 2], [4, 2, 13, 15], [2, 3, 12, 14, 11, 1], [5, 13, 15, 4], [6, 12, 9, 15], [11, 9, 15, 13], [10, 8, 12, 5], [2, 9], [10, 11, 8, 12]] 2 3 1 9 2 14 9 3 6 11 12 9 11 15 10 5 [0, 2, 3, 1, 9, 2, 14, 9, 3, 6, 11, 12, 9, 11, 15, 10, 5, 0] [[1, 4], [4, 0], [7, 8], [], [0, 1, 8, 10], [7, 13], [], [5, 2], [4, 2, 13, 15], [], [13, 4], [], [15, 13], [10, 8, 12, 5], [], [8, 12]] 1 4 [0, 1, 4, 0] [[], [], [7, 8], [], [8, 10], [7, 13], [], [5, 2], [4, 2, 13, 15], [], [13, 4], [], [15, 13], [10, 8, 12, 5], [], [8, 12]] 7 5 13 10 4 8 [2, 7, 5, 13, 10, 4, 8, 2] [[], [], [], [], [], [], [], [], [13, 15], [], [], [], [15, 13], [8, 12], [], [8, 12]] 13 12 15 [8, 13, 12, 15, 8] [[], [], [], [], [], [], [], [], [], [], [], [], [], [], [], []] ---- [] [[0, 2, 3, 1, 9, 2, 14, 9, 3, 6, 11, 12, 9, 11, 15, 10, 5, 0], [0, 1, 4, 0], [2, 7, 5, 13, 10, 4, 8, 2], [8, 13, 12, 15, 8]] yeah! no! [1, 2, 3, 4, 5, 6, 7, 8, 9] [[0, 2, 3, 1, 9, 2, 14, 9, 3, 6, 11, 12, 9, 11, 15, 10, 5, 0], [0, 1, 4, 0], [2, 7, 5, 13, 10, 4, 8, 2], [8, 13, 12, 15, 8]] [[0, 1, 4, 0, 2, 7, 5, 13, 10, 4, 8, 13, 12, 15, 8, 2, 3, 1, 9, 2, 14, 9, 3, 6, 11, 12, 9, 11, 15, 10, 5, 0]]
Deswegen, weil das so ist und wir so oder so nicht angenehm sind, koennen wir jetzt weiter machen und zeichne, die Eulertour jetzt noch mal zur probe ein
Ja, jetzt sieht man, wir muessen doch noch eine 1 zu den Knoten Namen Nummern bezeichnungen addieren.
adj_lst = [[3,2,6,5],[4,10,5,1],[1,4,15,10,8,9],[3,2,10,7],[1,2,9,11],[1,8,14,11],[4,12],[6,3],[5,3,14,16],[3,4,13,15,12,2],[6,14,16,5],[7,13,10,16],[12,10,16,14],[11,9,13,6],[3,10],[11,12,9,13]]
# also, ich habe jetzt erst mal diesen Eulergraphen von mir genommen und in eine Adjanzenzliste fuer Python 3 umgewandelt. Der Nachteil. Python faengt bei 0 an zu zaehlen, bei den Knoten V Vertices habe ich bei 1 angefangen. Das loese ich mit Python, ich erzeuge eine Kopie der Liste und subtrahiere in der Kopie von jedem Zustand, die Zahl 1.
# Mit len fuer jede Liste in der Liste ist das kein Problem auch, wenn die Listen innerhalb unterschiedliche Laengen haben, 2, 4, und 6
# Nachher wird der Algorithmus einfach so aussehen, angefangen bei einem Zustand gehe ich immer weiter, immer weiter bis ich am Ausgangsknoten angekommen bin, dabei entferne ich, das in Python eben ganz einfach moeglich, sowohl u und v einer Kante (u,v) und zwar das v bei u und das u bei v. Nichts ist in Python einfacher als das. Da es ein Eulergraph ist, muss ich wohl oder uebel irgendwann wieder am Ausgangsknoten ankommen, was vollkommen legitim ist, auch mit nur einem Kreis habe ich mein Ziel erreicht, habe ich allerdings - bzw. mein Programm so gewaehlt, dass ich nicht die ganze List leer habe, wenn ich wieder da bin, dann sehe ich die Liste ist nicht leer und beginne diese Ebenso zu bearbeiten
# im letzten Schritt, kopiere ich alle Listen der Reihe nach ineinander an die entsprechenden Knoten, was in Python kein Problem ist
# und im allerletzten Schritt, mache ich aus dieser Schachtelung von Listen eine einzige
import copy
a = copy.deepcopy (adj_lst)
print (adj_lst)
print (a)
i = 0
while i < len (a):
j = 0
while j < len (a[i]):
a [i][j] = a [i][j] - 1
j = j + 1
i = i + 1
print (a)
flag = False
start_v = []
circles = []
while flag == False:
euler = []
v0 = 0
while (v0 < len (a)) and not a[v0]:
v0 = v0 + 1
if v0 < len (a):
start_v.append (v0)
v = v0
u = a [v][0]
euler.append (v)
start_v = []
while u != v0:
print (u)
euler.append (u)
a [u].remove (v)
a [v].remove (u)
v = u
u = a [u][0]
a [u].remove (v)
a [v].remove (u)
euler.append (u)
print (euler)
print (a)
circles.append (euler)
else:
flag = True
print ("----")
print (start_v)
print (circles)
# test
b = [1,2,3,[4,5,6],7,8,9]
if type (b) == list:
print ("yeah!")
if type (b [0]) == list:
print ("yeah!")
else:
print ("no!")
def merge (b):
i = 0
while i < len (b):
#print (b [i])
if type (b [i]) == list:
if len (b [i]) > 0:
b [i].reverse ()
x = b[i].pop ()
b [i].reverse ()
b.insert (i,x)
# b [i] = x
i = i + 1
b.remove ([])
return b
merge (b)
print (b)
print (circles)
j = 0
while j < len (circles [0]):
i = 1
while i < len (circles):
if circles [0][j] == circles [i][0]:
circles [0][j] = circles [i]
merge (circles [0])
circles.remove (circles [i])
i = i + 1
j = j + 1
print (circles)
eulertour = copy.deepcopy (circles[0])
i = 0
while i < len (eulertour):
eulertour [i] = eulertour [i] + 1
i = i + 1
print (eulertour)
[[3, 2, 6, 5], [4, 10, 5, 1], [1, 4, 15, 10, 8, 9], [3, 2, 10, 7], [1, 2, 9, 11], [1, 8, 14, 11], [4, 12], [6, 3], [5, 3, 14, 16], [3, 4, 13, 15, 12, 2], [6, 14, 16, 5], [7, 13, 10, 16], [12, 10, 16, 14], [11, 9, 13, 6], [3, 10], [11, 12, 9, 13]] [[3, 2, 6, 5], [4, 10, 5, 1], [1, 4, 15, 10, 8, 9], [3, 2, 10, 7], [1, 2, 9, 11], [1, 8, 14, 11], [4, 12], [6, 3], [5, 3, 14, 16], [3, 4, 13, 15, 12, 2], [6, 14, 16, 5], [7, 13, 10, 16], [12, 10, 16, 14], [11, 9, 13, 6], [3, 10], [11, 12, 9, 13]] [[2, 1, 5, 4], [3, 9, 4, 0], [0, 3, 14, 9, 7, 8], [2, 1, 9, 6], [0, 1, 8, 10], [0, 7, 13, 10], [3, 11], [5, 2], [4, 2, 13, 15], [2, 3, 12, 14, 11, 1], [5, 13, 15, 4], [6, 12, 9, 15], [11, 9, 15, 13], [10, 8, 12, 5], [2, 9], [10, 11, 8, 12]] 2 3 1 9 2 14 9 3 6 11 12 9 11 15 10 5 [0, 2, 3, 1, 9, 2, 14, 9, 3, 6, 11, 12, 9, 11, 15, 10, 5, 0] [[1, 4], [4, 0], [7, 8], [], [0, 1, 8, 10], [7, 13], [], [5, 2], [4, 2, 13, 15], [], [13, 4], [], [15, 13], [10, 8, 12, 5], [], [8, 12]] 1 4 [0, 1, 4, 0] [[], [], [7, 8], [], [8, 10], [7, 13], [], [5, 2], [4, 2, 13, 15], [], [13, 4], [], [15, 13], [10, 8, 12, 5], [], [8, 12]] 7 5 13 10 4 8 [2, 7, 5, 13, 10, 4, 8, 2] [[], [], [], [], [], [], [], [], [13, 15], [], [], [], [15, 13], [8, 12], [], [8, 12]] 13 12 15 [8, 13, 12, 15, 8] [[], [], [], [], [], [], [], [], [], [], [], [], [], [], [], []] ---- [] [[0, 2, 3, 1, 9, 2, 14, 9, 3, 6, 11, 12, 9, 11, 15, 10, 5, 0], [0, 1, 4, 0], [2, 7, 5, 13, 10, 4, 8, 2], [8, 13, 12, 15, 8]] yeah! no! [1, 2, 3, 4, 5, 6, 7, 8, 9] [[0, 2, 3, 1, 9, 2, 14, 9, 3, 6, 11, 12, 9, 11, 15, 10, 5, 0], [0, 1, 4, 0], [2, 7, 5, 13, 10, 4, 8, 2], [8, 13, 12, 15, 8]] [[0, 1, 4, 0, 2, 7, 5, 13, 10, 4, 8, 13, 12, 15, 8, 2, 3, 1, 9, 2, 14, 9, 3, 6, 11, 12, 9, 11, 15, 10, 5, 0]] [1, 2, 5, 1, 3, 8, 6, 14, 11, 5, 9, 14, 13, 16, 9, 3, 4, 2, 10, 3, 15, 10, 4, 7, 12, 13, 10, 12, 16, 11, 6, 1]
[[0, 2, 3, 1, 9, 2, 14, 9, 3, 6, 11, 12, 9, 11, 15, 10, 5, 0], [0, 1, 4, 0], [2, 7, 5, 13, 10, 4, 8, 2], [8, 13, 12, 15, 8]] [[0, 1, 4, 0, 2, 7, 5, 13, 10, 4, 8, 13, 12, 15, 8, 2, 3, 1, 9, 2, 14, 9, 3, 6, 11, 12, 9, 11, 15, 10, 5, 0]]