Ich arbeite mit einem kleinen Rätsel:
Gegeben ein Wörterbuch mit Tupeln für Schlüssel: dictionary = {(p,q):n} , ich muss eine Liste neuer Wörterbücher jeder Kombination erzeugen, so dass sich weder p noch q innerhalb des neuen Wörterbuchs wiederholen. Und während der Erstellung dieser Liste von Wörterbüchern oder danach, wählen Sie eines der Wörterbücher als das gewünschte basierend auf einer Berechnung mit den Wörterbuchwerten.
Beispiel was ich meine (aber viel kleiner):
dictionary = {(1,1): 1.0, (1,2): 2.0, (1,3): 2.5, (1,4): 5.0, (2,1): 3.5, (2,2): 6.0, (2,3): 4.0, (2,4): 1.0}
wird
listofdictionaries = [{(1,1): 1.0, (2,2): 6.0}, {(1,1): 1.0, (2,3): 4.0}, (1,1): 1.0, (2,4): 1.0}, {(1,2): 2.0, (2,1): 3.5}, {(1,2): 2.0, (2,3): 4.0}, usw.
ein Wörterbuch wie: {(1,1): 1.0, (2,1): 3.5} ist nicht zulässig, weil q wiederholt.
Nun meine schluchzende Geschichte: Ich bin ganz neu beim Programmieren ... aber ich habe versucht, dieses Skript zu schreiben, um einige meiner Daten zu analysieren. Aber ich denke auch, dass es ein interessantes Algorithmusrätsel ist. Ich habe etwas geschrieben, das mit sehr kleinen Wörterbüchern funktioniert, aber wenn ich ein großes eingabe, dauert es viel zu lange (unten kopiert). In meinem Skriptversuch habe ich tatsächlich eine Liste von Kombinationen von Tupeln erzeugt, die ich später im Skript als Verweis auf mein Hauptwörterbuch verwende. Ich werde es unten kopieren:
Die Wörterbuch-Tupelschlüssel wurden mit zwei Listen generiert: "ExpList1" und "ExpList2"
%Vor%Nachdem ich diese Liste erstellt habe, wende ich eine Funktion an alle Wörterbuchkombinationen an (indem ich durch die Tupel-Listen iteriere und ihre entsprechenden Werte aus dem Hauptwörterbuch abrufe) und wähle die Kombination mit dem kleinsten resultierenden Wert aus dieser Funktion.
Ich habe auch versucht, die Funktion anzuwenden, während ich durch die Kombinationen iteriere, die die eindeutigen p, q-Einsen auswählen und dann überprüfe, ob der resultierende Wert kleiner als der vorherige ist und ihn beibehält (anstatt diese Liste zu erzeugen) uniquecombolist ", Am Ende erzeuge ich nur die letzte Tupel-Liste) - dauert immer noch zu lange.
Ich denke, die Lösung liegt in der Einbettung der Funktion p, q-no-repeat und der endgültigen Auswahl WÄHREND der Erzeugung von Kombinationen. Ich habe nur Mühe, meinen Kopf darum zu wickeln, wie man das wirklich macht.
Danke fürs Lesen! Sara
BEARBEITEN:
Um dies zu verdeutlichen, habe ich eine Alternative zu meinem Code geschrieben, die die endgültige Funktion (im Grunde die quadratischen Mittelwerte) zu den Paaren von Paaren enthält.
%Vor%Wenn ich also die RMS-Berechnung während der Satzgenerierung integrieren könnte und nur die kleinste beibehalten würde, würde ich damit mein kombinatorisches Problem lösen.
Wenn ich Ihr Problem verstanden habe, sind Sie an allen möglichen Kombinationen von Paaren (p, q) mit eindeutigen p und q interessiert, die eine gegebene Menge möglicher Werte für p und q respektieren. In meiner Antwort nehme ich an, dass diese möglichen Werte jeweils in list_p und list_q sind (Ich denke, das ist, was Sie in ExpList1 und ExpList2 haben, habe ich recht?)
Lassen Sie es mich wissen, wenn Sie danach suchen. Übrigens willkommen in SO, gute Frage!
Bearbeiten:
Wenn Sie befürchten, dass Ihre Liste enorm werden könnte, können Sie immer einen Generatorausdruck verwenden und die gewünschte Funktion darauf anwenden, z. B.
%Vor%Wenn Sie Generatoren anstelle von Listen verwenden, werden die Werte so berechnet, wie sie benötigt werden. Da wir an dem Mindestwert interessiert sind, wird jeder Wert berechnet und sofort verworfen, es sei denn, es ist das Minimum.
Diese Antwort setzt voraus, dass Sie versuchen, mit | S | Sets zu erzeugen Elemente, wobei S der kleinere Pool von Tupelkoordinaten ist. Der größere Pool wird mit L bezeichnet.
Da die Menge | S | enthält Paare mit nicht wiederholten Elementen, jedes Element von S muss genau einmal vorkommen. Setzen Sie von hier aus die Permutationen von L mit | S | Elemente werden mit den geordneten Elementen von S ausgewählt. Dies erzeugt alle angeforderten Mengen erschöpfend und ohne Wiederholung .
Beachten Sie, dass P (| L |, | S |) gleich | L |! / (| L | - | S |)!
istAbhängig von den Größen der Tupelkoordinatenpools können zu viele Permutationen zum Aufzählen vorhanden sein.
Ein Code zum Replizieren dieser Enumeration könnte folgendermaßen aussehen:
%Vor%Insgesamt könnte Ihr endgültiger Code etwa wie folgt aussehen:
%Vor%Wenn Sie dadurch nicht in eine Größenordnung oder zwei der gewünschten Laufzeit kommen, müssen Sie möglicherweise einen Algorithmus in Betracht ziehen, der keine optimale Lösung darstellt.
Tags und Links python combinations python-3.x python-2.7 itertools