Durch Dictionaries iterieren

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
psychodad

Mittwoch 30. März 2005, 11:14

Hi,

also ich möchte ein C++ Programm in ein Python neu schreiben, jetzt stehe ich jedoch vor einem Problem. In dem C++ Programm kommt folgender Code vor.

Code: Alles auswählen

void backtrack(map m, aktKnoten ) {
 // ...
 // rekursiver Aufruf 
 backtrack(m, nächsterKnoten(aktKnoten));
}
// ...
map m;
backtrack(m, m.first_node());
Das ist Pseudo-C++-Code, da ich nicht weiß ob hier alle C++ können.
Also die Klasse 'map' entspricht in der dictionary-Klasse aus Python, in dem Backtrackingalgorithmus muss ich die Elemente der Map einzeln durchlaufen.
In Python sieht dass bei mir in etwas so aus.

Code: Alles auswählen

def backtrack(dict, cur): 
  value = cur
  # do stuff ...
  # rekursiver Aufruf
  try:
    backtrack(dict, cur.next())
  except StopIteration:
    pass # Keine weiteren Elemente
# ...
# Aufruf
backtrack(d, iter(d))
Das funktioniert auch, nur sieht das für mich wie ein schlechter 'Hack' aus, denn ich setze hier eine Exception als 'reguläres' Mittel zu Steuerung des Programmflusses ein. Nun sind Exception aber nur zum Abfangen von Fehlern da, und nicht zum festlegen von Programmabläufen wenn keine Fehler auftreten, das oben ist also ganz mieser Stil. Da gibt es doch bestimmt eine bessere Lösung?

PS: Falls diese Frage trivial ist, bin relativ neu in Python.

Danke, Stefan
leoel
User
Beiträge: 36
Registriert: Dienstag 25. Mai 2004, 08:54
Wohnort: Graz

Mittwoch 30. März 2005, 11:52

Probier doch mal aus, dass Dir 'backtrack' einen Rückgabewert gibt:

Code: Alles auswählen

def backtrack(...):
    if not <Abbruchbedingung>:
        backtrack(...)
==> so (oder so ähnlich) sollte es gehen...
Gast

Mittwoch 30. März 2005, 12:19

Die Abbruchbedinung ist ja eben, dass alle Elemente durchlaufen wurden.
Wie frage ich den Ierator ab, ob er schon am Ende ist ??

Also nochmal in das Problem in Pseudocode:

Gegeben ist eine Liste, und nun möchte ich, mit einer Funktion, die sich rekursiv aufruft, die Elemente durchlaufen.

Code: Alles auswählen

backtrack( element )
 print element
 if noch Elemente in der Liste
  backtrack( nächstes Element ) # Mit nächstem Element aufrufen
Bsp.

Code: Alles auswählen

l = [ 'a','b','c','d' ]
backtrack( l.firstElement() )

sollte dann folgende Ausgabe erzeugen:

a
b
c
d

Das oben ist ja kein Pythoncode, sondern nur Pseudo. In C++ sieht das etwa so aus.

Code: Alles auswählen

void backtrack( list<string>::iterator it, list<string>::iterator end ) {
 cout << *it << endl;
 if( it != end ) {
  ++it;
  backtrack(it);
 }
}
// ...
list<string> li;
li.push_back("a");
li.push_back("b");
li.push_back("c");
li.push_back("d");
Hoffentlich ist jetzt klar was ich meine. Suche wie verrückt, aber finde keine passende, saubere Lösung, um dieses Kontrukt in Python umzusetzen.
CM
User
Beiträge: 2464
Registriert: Sonntag 29. August 2004, 19:47
Kontaktdaten:

Mittwoch 30. März 2005, 13:54

Hi

so ganz 100%ig ist mir nicht klar was Du willst. Über ein Dictionary iterieren? Warum nicht auf Pythonart:

Code: Alles auswählen

d = {1:'a',2:'b'}
for key in d: print d
#oder
for key,value in d.iteritems(): print key,value
Oder Du beschäftigst Dich mit Listen und willst reverse drüber gehen. Schau mal was das Tutorial dazu hergibt. Ein Beispiel:

Code: Alles auswählen

l = [1,2,3,4]
print l[::-1] #siehe Tutorial
#und dann dies
l.reverse()
print l
Du kannst natürlich auch einen rekursiven Algorithmus basteln. Aber warum von hinten durch die Brust ins Auge? Oder Du müsstest vielleicht doch noch mal Deine Motivation näher erläutern ...

Gruß und viel Spaß mit Python,
Christian
Gast

Mittwoch 30. März 2005, 14:50

Auf Pythonart iteriere ich ja linear durch die Elemente, ich will aber einen Suchbaum aufbauen. Und das macht üblicherweise mit Rekursion.

Okay, um vielleicht klar zu machen was ich will.

Code: Alles auswählen

def extendIso(sub, graph, cand, it):
 try:
  v  = it.next() # 'v' ist ein Knoten aus dem Untergraphen
  go = True
  print "Go on"
 except StopIteration:
  print "Stop"
  print cand
  go = False
  return True
 
 print "Extend: ", v
 for w in graph:
  print "Test: ", w
  # Kann der Knoten 'v' dem Knoten 'w' zugeordnet werden?
  if cand[v].has_key(w):
   #next = cand.copy() # TODO: Verifizieren, deepcopy?
   next = copy.deepcopy(cand)
   for i in next: # ??
    next[i] = copy.deepcopy(cand[i])
   print "Map %s to %s " % (v, w)
   # Ordne 'v' 'w' zu
   for x in sub:
    if x!=v and next[x].has_key(w):
     del next[x][w]
     
  # print "t: ", w
   
   for y in graph:
    if y!=w and next[v].has_key(y):
     del next[v][y]
  # print "OK"
   assert len(next[v]) == 1 and next[v].has_key(w), "Zuordnung OK"   
  # print "Ausgabe"
   # Ausgabe
   for x in sub:
   # print next.keys()   
    assert len(next[x])==1, "Zuordnung"
    print "{ %s, %s }" % ( x, next[x].keys() )
    if x == v:
     break
   if refineIso(sub, graph, next, v, w): # 1. Testen, ob Lösung legal
    return extendIso(sub, graph, next, it)  # 2. Weitersuchen
 return False
Das ist der aktuelle Code aus meinem Projekt.
Unter 1) und 2) sind die relevanten Backtrackingteile.
leoel
User
Beiträge: 36
Registriert: Dienstag 25. Mai 2004, 08:54
Wohnort: Graz

Mittwoch 30. März 2005, 15:32

Könntest Du vielleicht in Worten erklären, was Du machen willst. Ich habe nämlich keine Ahnung, was Dein Problem ist

Wenn es gar nicht anders geht, machst Du es eben nicht über .next() sondern über eine Zählvariable und du überprüfst halt, ob Du das Ende des Dictionarys erreicht hast.

(ist aber auch nicht hübsch...)
CM
User
Beiträge: 2464
Registriert: Sonntag 29. August 2004, 19:47
Kontaktdaten:

Mittwoch 30. März 2005, 15:37

Kann mich leoels Worten nur anschließen. Auch wenn ich mittlerweile so ungefähr zu verstehen glaube wohin die Reise geht, ist es ein wenig schwierig Deinen Wunsch nachzuvollziehen, ohne ihn zu kennen. Und wenn Du nur eine Funktion pastest, solltest Du vielleicht auch noch genau schreiben, was das für Parameter sind, die übergeben werden, und was herauskommen soll (würde ich ja in einem C++-Forum nicht anders machen ;-) ), ggf. auch mittels einer Testfunktion.

Gruß,
Christian
Benutzeravatar
jens
Moderator
Beiträge: 8461
Registriert: Dienstag 10. August 2004, 09:40
Wohnort: duisburg
Kontaktdaten:

Mittwoch 30. März 2005, 15:49

psychodad hat geschrieben:

Code: Alles auswählen

def backtrack(dict, cur): 
  value = cur
  # do stuff ...
  # rekursiver Aufruf
  try:
    backtrack(dict, cur.next())
  except StopIteration:
    pass # Keine weiteren Elemente
# ...
# Aufruf
backtrack(d, iter(d))
Ich weiß auch nicht so recht, was gemacht werden soll, aber try und StopIteration kommt mir sehr komisch vor...
Warum nicht einfach den rekursiven Aufruf nur unter der Bedingung machen, wenn weitere Daten vorhanden sind:

Code: Alles auswählen

def backtrack(dict, cur):
  value = cur
  # do stuff ...
  # rekursiver Aufruf
  if da gibts noch mehr == True:
    backtrack(dict, cur.next())

backtrack(d, iter(d))
Tip: Such doch einfach mal im Forum nach "rekursiv" vielleicht siehst du da Codeschnipsel, die dir weiter helfen!

CMS in Python: http://www.pylucid.org
GitHub | Open HUB | Xing | Linked in
Bitcoins to: 1JEgSQepxGjdprNedC9tXQWLpS424AL8cd
joe

Mittwoch 30. März 2005, 16:01

jens hat geschrieben: Ich weiß auch nicht so recht, was gemacht werden soll, aber try und StopIteration kommt mir sehr komisch vor...
Das ist schon ok so. "StopIteration" ist für die programmablaufsteuerung vorgesehen. Deshalb sind "StopIteration" und "SystemExit" auch die einzigen buildin-ausnahmen, die nicht von "StandardError" erben, sondern direkt von "Exception".
joe
psychodad

Mittwoch 30. März 2005, 17:30

Ja, einfach den Quellcode zu posten ist sicherlich nicht besonders schlau, da ist viel dabei was nicht zum Problem gehört und es zu erklären würde hier vielleicht den Rahmen sprengen.

Aber glücklicherweise scheint ihr schon verstanden zu haben, worum es geht.

Also eine Zählvariable wäre prinzipiell möglich, nur ist das nicht ineffizient, auf die Elemente in einem Dictionary jedesmal mit einem Index zuzugreifen?? Dann müsste am Anfang meiner Funktion in etwa folgendes stehen bzw. folgende Funktion müsste ich nutzen.

Code: Alles auswählen

def getElement(offset, dict):
 for x in dict:
  ++i
   if i == offset:
     return x
Ja, und das mit der Exception scheint mir nicht nur vom Design schlecht zu sein, es ist auch so umständlich. Normalerweise wird doch immer gesagt Pythonkontrukte sind besonders elegant, aber das find ich nicht elegant.

Achja. und nur eine Bedingung? Wie soll das gehen?
Ja, ich muss doch immer auf das aktuelle Element in dem Dictionary zugreifen, und das durchlaufen tue ich in den rek. Aufrufen.

Achso, das Programm ist zum Test auf Graphenisomorphie. Eine Beschreibung des Algorithmus gibt es hier.
http://www.strange-phenomenom.de/pmwiki ... Isomorphie
Wie man sieht eine klassische Tiefensuche bzw. Backtracking, wie man es aus der typ. Informatik-Algorithmen&Datenstrukturen-Vorlesung kennt
Benutzeravatar
jens
Moderator
Beiträge: 8461
Registriert: Dienstag 10. August 2004, 09:40
Wohnort: duisburg
Kontaktdaten:

Mittwoch 30. März 2005, 19:49

Aha... Backtracking mußte ich erstmal nachschauen:
http://de.wikipedia.org/wiki/Backtracking

Ach, vielleicht hilft dir .pop() weiter...

CMS in Python: http://www.pylucid.org
GitHub | Open HUB | Xing | Linked in
Bitcoins to: 1JEgSQepxGjdprNedC9tXQWLpS424AL8cd
Gast

Mittwoch 30. März 2005, 20:07

dann würde ich ja die elemente aus meinem dictionary entfernen, dass will ich aber nicht unbedingt.

Prinzipiell wäre das schon möglich, aber nebenbei müsste ich dann auch viele kopien von meinem dictionary machen, da ja jeder Lösungsweg, den ich "Rückverfolge" sein eigenes unveändertes Dictionary brauch.
BlackJack

Donnerstag 31. März 2005, 06:18

Dein Code sieht aber doch ein wenig(?) anders aus als der Algorithmus unter der angegebenen URL.

Musst Du denn wirklich einen Iterator beim Aufruf übergeben? Kannst Du das nicht in einer Schleife lösen in der dann der rekursive Aufruf mit nur einem Element gemacht wird? In dem Beispielcode auf der Wiki-Seite wird das jedenfalls so gemacht.

Was an dem C++ Quelltext furchtbar ist, sind die ``while``-Schleifen. Die sollte man unter Python ganz dringend surch ``for``-Schleifen ersetzen. Ich weiss gar nicht warum das nicht auch im C++ Quelltext gemacht wurde. Dann wäre der Algorithmus IMHO viel lesbarer/verständlicher.

Willst Du eine Lösung finden, also am Ende eine Abbildung von Knoten aus Graph A auf Knoten von Graph B haben, oder wie im Beispiel nur wissen ob es überhaupt eine Lösung gibt?

Wenn man mal davon absieht, dass in der `IsomorphieSuche()` ein Rekursionsanker fehlt, ist das ziemlich einfach nach Python umzusetzen. Sieht bei mir aber komplett anders aus als der Quelltext, den Du hier gepostet hast!?
CM
User
Beiträge: 2464
Registriert: Sonntag 29. August 2004, 19:47
Kontaktdaten:

Donnerstag 31. März 2005, 08:48

Hoi,

kann mich so manchem Vorschlag wieder mal nur anschließen. Eine Bemerkung kann ich mir denn doch aber nicht verkneifen: Vermeide doch bitte Schlüsselwörter wie "dict" im Code, wenn Du es nicht mußt. Du überschreibst doch auch in C/C++ nicht Funktionen wie "assert" oder "malloc", wenn Du nicht mußt ;-).

Mit Sicherheit von Interesse ist von folgendes Essay von Guido von Rossum. Etwas veraltet wie Du feststellen wirst, aber vielleicht ... Und sonst google mal mit "Python graph theory".

Außerdem gibt es noch "Algorithms in C" von O'Reilly mit einer Einführung zu Graphen: Mir ist aufgefallen, daß man dies sehr leicht in Python übersetzen kann.

Gruß,
Christian
psychodad

Donnerstag 31. März 2005, 12:02

Ja, mein Algorithmus arbeitet etwas anders als der in dem Script angegebene. Es ist mir nicht gelungen denn aus dem Script 1 zu 1 umzusetzen, meiner basiert eher auf einem Algorithmus aus "Algorithms on Trees and Graphs" von Gabriel Valiente.

Mich interessiert nur ob eine Lösung existiert, die genaue Abbildung brauche ich nicht unbedingt.

"Musst Du denn wirklich einen Iterator beim Aufruf übergeben? Kannst Du das nicht in einer Schleife lösen in der dann der rekursive Aufruf mit nur einem Element gemacht wird? In dem Beispielcode auf der Wiki-Seite wird das jedenfalls so gemacht. "

Gelingt mir eben nicht, auch wenn es in dem Script so beschrieben wird.

Code: Alles auswählen

def extendIso(sub, graph, cand, it):
 # ...
 if refineIso(sub, graph, next, v, w): # 1. Testen, ob Lösung legal
    return extendIso(sub, graph, next, it)  # 2. Weitersuchen
Wenn ich mit einer äußeren Schleife die Knoten durchgehe, dann suche ich ja nicht in jedem "Zweig" des Suchbaumes weiter. Vielleicht gibt es da eine einfache algorithmische Formulierung (wie z.B. in dem Script) aber mir ist diese Umsetzung nicht gelungen.

Abgesehen davon lief das in meinem C++ Programm so auch wunderbar, mich stört halt nur dieses umständliche explizite (also nicht mit einer for-Schleife) iterieren durch das Dictionary.

PS: Ja, sorry, hab grad nicht dran gedacht, dass dict ein Schlüsselwort ist. Wie gesagt, bin noch relativer neu im Umgang mit Python.
Antworten