Listenelemente vergleichen und zusammenziehen...

[polypus]

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.

[Craven]

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.

[polypus]

Stimmt natürlich. Aber die Sortierung soll keinen Einfluss auf das Ergebnis haben.

[Craven]

Wie sieht die compare_function aus?

[numerix]

@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]

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_))

[numerix]

Wie sieht die compare_function aus?

Das ist doch für die Problemlösung unwichtig.

[Craven]

Das ist doch für die Problemlösung unwichtig.

Wenn du das sagst.

[polypus]

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]

Was macht das besser als mein Variante? (Mal abgesehen davon, komplex und ubübersichtlich zu sein)

[polypus]

öhm... muss das besser sein?

[audax]

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