Listenelemente vergleichen und zusammenziehen...

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.
polypus
User
Beiträge: 37
Registriert: Dienstag 27. September 2005, 14:11
Wohnort: Salzburg

Listenelemente vergleichen und zusammenziehen...

Beitragvon polypus » Freitag 16. Januar 2009, 13:02

Ich hab ein kleines Problem das vermutlich leicht lösbar ist, aber ich habe irgendwo einen Knoten im Hirn.
Ich habe eine Liste mit x elementen. Weiters eine Funktion, die zwei Listenelemente miteinander vergleichen kann und eine 0/1 aussage trifft, ob zwei listenelemente "komplexiert" werden.
Ein "Komplex" sollte dann ein neues Listenelement darstellen und die Entitäten, aus denen er gebildet wurde sollen aus der Liste gelöscht werden.
Vergleiche mit sich selber sind ausgeschlossen.

Welche Schleifenform kann ich da verwenden? Brauche ich eine doppelte for Schleife? Wie komm ich da wieder raus? mit continue? Soll ich das Rekursiv lösen? Was wär da dann die Abbruchbedingung? Ich denk da irgendwie im Kreis oder generell falsch... :(

Zur Veranschaulichung:

Code: Alles auswählen

Liste = ['A', 'B', 'C', 'D']
for i in Liste:
    for j in Liste:
        if i != j:
            if compare_function(i, j) == 1:
                Liste.append(i+j)
                Liste.remove(i); Liste.remove(j)
                #wie komm ich da jetzt wieder raus? :)
                #neue Liste sollte jetzt so ausschauen ['AB', 'C', 'D']


Oder muss ich da einen gänzlich anderen Weg gehen? Die Listen können wohl bis zu 60 Elemente lang werden... so ca.
Benutzeravatar
Craven
User
Beiträge: 223
Registriert: Dienstag 24. Januar 2006, 13:37

Re: Listenelemente vergleichen und zusammenziehen...

Beitragvon Craven » Freitag 16. Januar 2009, 13:21

polypus hat geschrieben:

Code: Alles auswählen

#neue Liste sollte jetzt so ausschauen ['AB', 'C', 'D']


Das neue Element wird doch durch append hinten angehängt, d.h. du müsstest die Reihenfolge noch ändern, falls dich das stört.

Code: Alles auswählen

#neue Liste sollte jetzt so ausschauen ['C', 'D', 'AB']


Nur so am Rande.

Code: Alles auswählen

q = 'q = %s; print q %% repr(q)'; print q % repr(q)
polypus
User
Beiträge: 37
Registriert: Dienstag 27. September 2005, 14:11
Wohnort: Salzburg

Beitragvon polypus » Freitag 16. Januar 2009, 13:26

Stimmt natürlich. Aber die Sortierung soll keinen Einfluss auf das Ergebnis haben.
Benutzeravatar
Craven
User
Beiträge: 223
Registriert: Dienstag 24. Januar 2006, 13:37

Beitragvon Craven » Freitag 16. Januar 2009, 13:30

Wie sieht die compare_function aus?

Code: Alles auswählen

q = 'q = %s; print q %% repr(q)'; print q % repr(q)
Benutzeravatar
numerix
User
Beiträge: 2696
Registriert: Montag 11. Juni 2007, 15:09

Beitragvon numerix » Freitag 16. Januar 2009, 13:32

@polypus: Ist dir bewusst, dass dein Ergebnis davon abhängt, in welcher Reihenfolge deine Elemente in der Liste vorkommen? Ist das gewollt? Sind es zufällig immer benachbarte Elemente, die "komplexiert" werden?

Und: Wieso willst du da "wieder raus"?
Was ist mit "C"+"D" -> "CD"?
Oder: Warum nimmst du nicht eine neue Liste für die "komplexierten" Ergebnisse?
Und: Das ändern der Liste, über die man iteriert, während des Iterierens halte ich auch für keine gute Lösung.
audax
User
Beiträge: 830
Registriert: Mittwoch 19. Dezember 2007, 10:38

Beitragvon audax » Freitag 16. Januar 2009, 13:33

Code: Alles auswählen

def cmp_(a,b):
    return ord(a) - ord(b) == -1

lst = ['A', 'B', 'D', 'F']

def transform(lst, compare):
    allready = set()
    for idx,outer in enumerate(lst):
        for inner in lst[idx+1:]:
            if inner not in allready and compare(outer, inner):
                allready.add(inner)
                yield outer + inner
                break
        else:
            yield outer

print list(transform(lst, cmp_))

Benutzeravatar
numerix
User
Beiträge: 2696
Registriert: Montag 11. Juni 2007, 15:09

Beitragvon numerix » Freitag 16. Januar 2009, 13:33

Craven hat geschrieben:Wie sieht die compare_function aus?


Das ist doch für die Problemlösung unwichtig.
Benutzeravatar
Craven
User
Beiträge: 223
Registriert: Dienstag 24. Januar 2006, 13:37

Beitragvon Craven » Freitag 16. Januar 2009, 13:38

numerix hat geschrieben:Das ist doch für die Problemlösung unwichtig.

Wenn du das sagst.

Code: Alles auswählen

q = 'q = %s; print q %% repr(q)'; print q % repr(q)
polypus
User
Beiträge: 37
Registriert: Dienstag 27. September 2005, 14:11
Wohnort: Salzburg

Beitragvon polypus » Samstag 17. Januar 2009, 12:21

Das Ganze geht eingentlich mit einer Rekursion:

Code: Alles auswählen

#funktion compare gibt 0 oder 1 zurück; wie ist egal.

def concatenate_list(list):
    possible = (len(list)*(len(list-1))/2 # mögliche paare der liste
    for i in list:
        count = 0
        for j in list:
            if i !=j:
                count += 1
                if count != possible:
                    if compare(i,j):
                        list.append(i+j)
                        list.remove(i);list.remove(j)
                        return concatenate_list(list)
    return list


Code ist jetzt ungetestet. aber so ähnlich sollte es funktionieren.
Je mehr listenelemente im letzten durchlauf übrig bleiben, desto länger dauert die berechnung (O²).
audax
User
Beiträge: 830
Registriert: Mittwoch 19. Dezember 2007, 10:38

Beitragvon audax » Samstag 17. Januar 2009, 12:54

Was macht das besser als mein Variante? (Mal abgesehen davon, komplex und ubübersichtlich zu sein)
polypus
User
Beiträge: 37
Registriert: Dienstag 27. September 2005, 14:11
Wohnort: Salzburg

Beitragvon polypus » Sonntag 18. Januar 2009, 01:26

öhm... muss das besser sein?
audax
User
Beiträge: 830
Registriert: Mittwoch 19. Dezember 2007, 10:38

Beitragvon audax » Sonntag 18. Januar 2009, 13:14

Sonst wäre es doch sinnlos, es zu posten in dem Kontext, oder? Oo

Wer ist online?

Mitglieder in diesem Forum: Bing [Bot]