Nach gemeinsamen Sequenzen in Listen suchen

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.
Antworten
__marcus__
User
Beiträge: 92
Registriert: Mittwoch 10. September 2008, 22:10
Wohnort: Hamburg

Donnerstag 6. November 2008, 22:25

Code: Alles auswählen

[3,2,1,5,6,7]
[9,5,6,7,4,5]
[1,2,3,4,5,6]
[9,8,1,2,3,7]
[5,6,7,6,7,1]
Ich habe als Ergebnis eine Liste mit Listen und möchte jetzt aus diesen Listen alle Sequenzen haben, die sich wiederholen.

Hier wären das [5,6,7] und [1,2,3]

Die Sequenzen können aber auch aus mehr als 3 Elementen bestehen und die Elemente einer Sequenz und ihre Reihenfolge sind unbekannt.

Hat da wer vielleicht zumindest einen Ansatz für mich?
Benutzeravatar
numerix
User
Beiträge: 2696
Registriert: Montag 11. Juni 2007, 15:09

Donnerstag 6. November 2008, 22:32

Was meinst du mit "die Reihenfolge ist unbekannt"?

Das bezieht sich doch sicher auf die Listen (in der Liste), nicht auf die einzelnen int-Werte in den inneren Listen, oder?

Sind es immer 6 Elemente pro Liste?
Benutzeravatar
numerix
User
Beiträge: 2696
Registriert: Montag 11. Juni 2007, 15:09

Donnerstag 6. November 2008, 22:58

Für den Fall, dass ich dich richtig verstanden habe, sollte das funktionieren:

Code: Alles auswählen

listen = [[3,2,1,5,6,7], [9,5,6,7,6,5], [1,2,3,4,5,6], [9,8,1,2,3,7], [5,6,7,6,7,1]]
ergebnisse = []

for k in range(len(listen)):
    vglliste = listen.pop()
    for liste in listen:
        for m in range(3,len(vglliste)+1):
            for n in range(len(vglliste)-m+1):
                teil = vglliste[n:m+n]
                for p in range(len(liste)-m+1):
                    if teil == liste[p:p+m] and not teil in ergebnisse:
                        ergebnisse.append(teil)
print ergebnisse
Hier wird allerdings noch nicht berücksichtigt, dass beim wiederholten Vorkommen einer z.B. 4-elementigen Sequenz eine darin enthaltene 3-elementige Sequenz nicht trotzdem mit aufgenommen wird, und zwar auch dann, wenn diese 3-elementige Sequenz nur als Teil dieser 4-elementigen Sequenz wiederholt vorkommt.
Benutzeravatar
str1442
User
Beiträge: 520
Registriert: Samstag 31. Mai 2008, 21:13

Donnerstag 6. November 2008, 23:10

Du könntest aus allen Listen Mengen (sets) machen und deren einzelne Schnittmengen bilden. Dann für jedes Element in der Schnittmenge nach der Position in einer neuen Liste sortieren (zb über List Comprehension und enumerate), und dann schauen, ob die sich gleichen. Der erste Ansatz, der mir einfiel.

So ca:

Code: Alles auswählen

from itertools import izip

def list_subsets(list_one, list_two):
    compare_set = set(list_one) & set(list_two)
    last_index = 0
    new_list = []

    for index, (list_obj_one, list_obj_two) in enumerate(izip(list_one, list_two)):
        if list_obj_one in compare_set or list_obj_two in compare_set:
            if (index - 1) == last_index:
                new_list.append([list_obj_one, list_obj_two][list_obj_two in compare_set])
                last_index = index

    return new_list
Einige Dinge müsstest du aber noch anpassen, könnte auch sein das ich einige Verhaltensweisen übersehen hab.
__marcus__
User
Beiträge: 92
Registriert: Mittwoch 10. September 2008, 22:10
Wohnort: Hamburg

Donnerstag 6. November 2008, 23:30

numerix hat geschrieben:Was meinst du mit "die Reihenfolge ist unbekannt"?
Es kann auch sein, dass [89,27,1,709,12] die Sequenz ist, die gefunden werden muss. Und die Listen sind unterschiedlich lang.

Aber die Idee mit Sets ist glaube ich von daher schon mal ne gute Sache.
ichbinsisyphos
User
Beiträge: 120
Registriert: Montag 4. Juni 2007, 19:19

Freitag 7. November 2008, 01:54

__marcus__ hat geschrieben:
numerix hat geschrieben:Was meinst du mit "die Reihenfolge ist unbekannt"?
Es kann auch sein, dass [89,27,1,709,12] die Sequenz ist, die gefunden werden muss.
Das klingt jetzt mehr danach, dass die zu suchende Sequenz vorgegeben wird.
Oder willst du eher sowas wie die längste Sequenz direkt aufeinander folgenden Zahlen die in der selben Reihenfolge in jeder Liste auftreten?
Benutzeravatar
numerix
User
Beiträge: 2696
Registriert: Montag 11. Juni 2007, 15:09

Freitag 7. November 2008, 07:02

__marcus__ hat geschrieben:Aber die Idee mit Sets ist glaube ich von daher schon mal ne gute Sache.
Hast du meinen Code mal ausprobiert? Ich denke, das Programm macht, was du willst.
Benutzeravatar
str1442
User
Beiträge: 520
Registriert: Samstag 31. Mai 2008, 21:13

Freitag 7. November 2008, 07:36

Du schlägst dich im ersten Teil der Aufgabe unnötig mit der Reihenfolge der Listen herum. Du musst doch nur wissen, welche Objekte in beiden Listen vorkommen (und ob die mehr als einmal vorhanden sind spielt auch keien Rolle). Dann kannst du die Sequenzen filtern. Insofern ist mein Ansatz angepasster in Bezug auf das Problem. Nur der Filter Teil funktioniert nicht korrekt.
__marcus__
User
Beiträge: 92
Registriert: Mittwoch 10. September 2008, 22:10
Wohnort: Hamburg

Freitag 7. November 2008, 09:53

Ich hab mir das zwar noch immer nicht angeguckt, aber ich hab mal ein Beispiel gepastet, woran jeder trotz schlechter Erklärungen erkennt, was das Problem ist: http://paste.pocoo.org/show/90454/

Weg1 ist der kürzeste von A nach B (und hinter jedem Straßennamen steht natürlich eine Nummer.)

Wenn ich Weg1 kenne, versuche ich von jedem Punkt Weg1[n] = An einen Weg zu B zu finden in dem kein Punkt aus Weg1[n+1:-1] enthalten ist.

Das Ergebnis ist s.o.

Die Routen, die keine Gemeinsamkeiten mit anderen Routen haben, möchte ich so wie sie sind behalten und bei denen, die Gemeinsamkeiten haben, möchte ich quasi den größten gemeinsamen Streckenabschnitt erhalten, damit ich dann von diesen den kürzesten Weg zu A bzw. B errechnen kann. (Was bei langen Strecken in der Form natürlich nicht nur wegen der Rechenleistung nicht funktioniert, aber ich stehe da auch erst am Anfang...)

Und ich möchte halt nach Möglichkeit nicht mit den Strings arbeiten, weil ich die dann wieder umwandeln müsste in die IDs der Wege nach dem Herausfinden der gemeinsamen Streckenabschnitte...
Benutzeravatar
numerix
User
Beiträge: 2696
Registriert: Montag 11. Juni 2007, 15:09

Freitag 7. November 2008, 18:52

__marcus__ hat geschrieben:Ich hab mir das zwar noch immer nicht angeguckt, ...
Das verstehe ich nun nicht: Du postest ein Problem, bekommst sogar fertigen Code, von dem der, der ihn geschrieben hat, meint, dass dein Problem damit gelöst werden sollte, und guckst ihn dir nicht an ??? :roll:

Warum nimmst du nicht ein paar Beispieldaten und probierst zunächst einmal aus, ob der Code das als Ergebnis produziert, was du erwartest?
__marcus__
User
Beiträge: 92
Registriert: Mittwoch 10. September 2008, 22:10
Wohnort: Hamburg

Freitag 7. November 2008, 20:15

Ich hatte das eigentlich auch eher gepostet, weil ich das Gefühl hatte mich wieder mal völlig unverständlich ausgedrückt zu haben.

Mittlerweile hab ich mir das auch angeguckt und hat mich auch auf jeden Fall inspiriert bei meinem Problem. Auch wenn ich zu dem Schluß gekommen bin, schon beim Routing zu gucken wie sehr ein neuer Weg einem alten gleicht und gegebenenfalls einen Weg einfach nicht weiter zu verfolgen. (Was richtig Zeit spart...)

Danke sehr.
Antworten