Zweidimensionale Matrix nach Element durchsuchen

Chillee · Sonntag 8. Januar 2012, 15:40

Hallo liebe Python-Freunde,

ich sitze jetzt schon seit geraumer Zeit an einem Programm und ich komme einfach nicht weiter.

Die Aufgabe ist eine zweidimensional Matrix zu durchsuchen, welche die Eigenschaften hat x (i,j) <= x(i+1,j) sowie x(i,j) <= x(i,j+1) .
D.h. das Element darunter oder rechts davon ist mindestens gleich groß oder größer. Ich will nun einen Algorithmus anwenden der diese Eigenschaft ausnutzt, um ein Element zu finden.

Praktisch sieht das ganze im Moment so aus:

Code: Alles auswählen

#Initialisiere Beispielmatrix
mat = [None]*25
for i in range(25):
    mat[i] = [None]*25
    
mat = [
        [ 1, 2, 3, 4, 5],
        [ 9, 10, 15, 20, 21],
        [ 12, 19, 25, 31, 38],
        [ 14, 22, 26, 34, 40],
        [ 16, 24, 27, 36, 42],
        [ 17, 28, 32, 39, 44],
    ]

#Main-Funktion
def run():
    #Eingabe
    eing = int(raw_input("Welches Element suchen sie?: "))
    #Suche
    search(eing)
    #Ausgabe Matrix
    for ir in range(6):
        for ic in range(5):
            print mat[ir][ic],
        print

    
#Suchfunktion
def search(e):
    r = 0
    c = 0
    while e != mat[r][c]:
        if r < 24:
            if e < mat[r+1][c]:
                r += 1
            elif c < 24:
                if mat[r][c+1] > e:
                    r -= 1
                    c += 1
                elif mat[r][c+1] < e:
                    c += 1
            else:
                r -= 1
        else:
            c += 1
            r = 0
            

    ausg = "Reihe: "+str(r)+" | Spalte: "+str(c)
    print ausg 
                  

# Startroutine
if __name__ == '__main__':
    run()
    raw_input('[Enter] fuer Programmende druecken')

Nun komme ich ständig egal was für Ideen ich auch habe auf einen IndexError. (bei: if e < mat[r+1][c]

Ich mein...ja es ist bloß ein IndexError, aber ich verstehe nicht wo und warum?
Kann mir da jemand weiterhelfen?

Den Algorithmus möchte ich dann bitte selber anpassen und verbessern, also bitte verratet nicht zu viel

!

Vielen Dank schonmal!

Viele Grüße,

Chillee

Hyperion · Sonntag 8. Januar 2012, 16:16

Dann lass Dir doch einfach mal die beteiligten Variableninhalte ausgeben - dann siehst Du doch, welche Werte zum IndexError führen. Ist ein Wert zu groß, musst Du dann nachdenken, wieso das der Fall sein könnte.

BlackJack · Sonntag 8. Januar 2012, 16:19

@Chillee: Du hast eine Matrix, die ganz offensichtlich weniger als 25 Zeilen oder Reihen hat, und wunderst Dich bei *dem* Quelltext dass Du `IndexError`\s bekommst!?

Als ersten Schritt solltest Du da vielleicht mal diese „magischen“ literalen Zahlen aus dem Quelltext durch die zur Laufzeit ermittelten *tatsächlichen* Ausmasse ersetzen.

Bei der Gelegenheit sollte dann der Quelltext auf Modulebene der keine Konstanten (Werte, Funktionen, Klassen, etc.) definiert, in einer Funktion verschwinden lassen. `mat` IMHO gehört dazu, was zur Folge hat, dass man das Objekt auch sauber als Argument an `search()` übergeben muss.

Der Code ganz am Anfang ist überflüssig. Und so eine Initialisierung über Listen mit Platzhaltern die dann in einer Schleife durch die tatsächlichen Werte ersetzt werden, ist in Python unüblich. „Pythonischer“ wäre es die Listen gleich mit den entsprechenden Werten auf zu bauen. Wenn man die noch nicht hat, dann erstellt man auch die Liste noch nicht.

Chillee · Sonntag 8. Januar 2012, 16:38

@Hyperion: Danke, aber das habe ich schon probiert und komme leider der Lösung nicht näher.

@BlackJack:Danke erstmal!

BlackJack hat geschrieben:@Chillee: Du hast eine Matrix, die ganz offensichtlich weniger als 25 Zeilen oder Reihen hat, und wunderst Dich bei *dem* Quelltext dass Du `IndexError`\s bekommst!?

Als ersten Schritt solltest Du da vielleicht mal diese „magischen“ literalen Zahlen aus dem Quelltext durch die zur Laufzeit ermittelten *tatsächlichen* Ausmasse ersetzen.

Stimmt, ich habe jetzt die Initialisierung raus genommen und die Grenzen genau an die Matrix angepasst. Also r<6 und c<5 und dennoch der selbe Fehler.

Code: Alles auswählen

Traceback (most recent call last):
  File "...\datei.py", line 60, in <module>
    run()
  File "...\datei.py", line 25, in run
    search(eing)
  File "...\datei.py", line 39, in search
    if e < mat[r+1][c]:
IndexError: list index out of range

BlackJack hat geschrieben: Bei der Gelegenheit sollte dann der Quelltext auf Modulebene der keine Konstanten (Werte, Funktionen, Klassen, etc.) definiert, in einer Funktion verschwinden lassen. `mat` IMHO gehört dazu, was zur Folge hat, dass man das Objekt auch sauber als Argument an `search()` übergeben muss.

Der Code ganz am Anfang ist überflüssig. Und so eine Initialisierung über Listen mit Platzhaltern die dann in einer Schleife durch die tatsächlichen Werte ersetzt werden, ist in Python unüblich. „Pythonischer“ wäre es die Listen gleich mit den entsprechenden Werten auf zu bauen. Wenn man die noch nicht hat, dann erstellt man auch die Liste noch nicht.

Da geb ich dir recht ist unsauber, aber wie gesagt soll es eigentlich nur eine Textmatrix sein, um den Algorithmus zu testen.

Aber leider konnte ich immernoch nicht diesen IndexError los werden.

Soweit meine Anpassungen: (Hab ich alles richtig verstanden?)

Code: Alles auswählen

#Main-Funktion
def run():
    #Eingabe
    eing = int(raw_input("Welches Element suchen sie?: "))
    #Suche
    a = [
        [ 1, 2, 3, 4, 5],
        [ 9, 10, 15, 20, 21],
        [ 12, 19, 25, 31, 38],
        [ 14, 22, 26, 34, 40],
        [ 16, 24, 27, 36, 42],
        [ 17, 28, 32, 39, 44],
    ]
    search(eing, a)
    #Ausgabe Matrix
    for ir in range(6):
        for ic in range(5):
            print mat[ir][ic],
        print

    
#Suchfunktion
def search(e, mat):
    r = 0
    c = 0
    while e != mat[r][c]:
        if r < 6:
            if e < mat[r+1][c]:
                r += 1
            elif c < 5:
                if mat[r][c+1] > e:
                    r -= 1
                    c += 1
                elif mat[r][c+1] < e:
                    c += 1
            else:
                r -= 1
        else:
            c += 1
            r = 0
            

    ausg = "Reihe: "+str(r)+" | Spalte: "+str(c)
    print ausg 
                  

# Startroutine
if __name__ == '__main__':
    run()
    raw_input('[Enter] fuer Programmende druecken')

Hyperion · Sonntag 8. Januar 2012, 16:44

Chillee hat geschrieben:@Hyperion: Danke, aber das habe ich schon probiert und komme leider der Lösung nicht näher.

Du willst uns erzählen, dass Du print-Statements zum Debuggen vor die Stellen gesetzt hast, an denen der Fehler auftritt und dennoch keine Ahnung hast, wieso der Fehler zu stande kommt?

Gerade bei einem IndexError bietet sich das doch an - da die Ursache an sich offensichtlich ist und man letztlich prüfen muss, welche Werte die "Zugriffs"variablen tatsächlich besitzen.

Chillee · Sonntag 8. Januar 2012, 16:49

Moment...STOPP!!

Dicker Denkfehler...ich habs gleich!!!

Chillee · Sonntag 8. Januar 2012, 16:57

BlackJack lag voll und ganz richtig.

Wer natürlich vor lauter Eifrigkeit vergisst, dass die Indexzählung doch bei Null los geht, ist einfach selber schuld!

Jetzt funktioniert es!

@Hyperion: Ja ich hab die print Ausgabe doch gemacht, aber irgentwie hatte sie mir zu dem Zeitpunkt als ich sie durchgeführt habe nix genützt. Da ich in diesem Moment das Problem noch anders lösen wollte: Ich hatte eine feste Größe verteilt und nicht besetzt Elemente waren vom Type None und die Abbruchbedinungen hatte ich dann mit is not None lösen wollen. Ist jetzt auch egal, auf jeden Fall hast du Recht gehabt

!

Allso nochmals vielen herzlichen Dank euch beiden und noch einen schönen Sonntagabend!

Viele Grüße,
Chillee