Python: Wie alle Kombinationen von Listen von Tupeln zu erzeugen, ohne Inhalt des Tupels Wiederholung

Question

Ich bin mit ein bisschen ein Rätsel arbeiten:

ein Wörterbuch mit Tupeln für Schlüssel Gegeben: dictionary = {(p,q):n}, ich brauche eine erzeugen Liste neuer Wörterbücher jeder Kombination, so dass sich weder p noch q innerhalb des neuen Wörterbuchs wiederholen. Und während der Erzeugung dieser Liste von Wörterbüchern oder danach, wähle eines der Wörterbücher als das gewünschte aus, basierend auf einer Berechnung unter Verwendung der Wörterbuchwerte.

Beispiel dafür, 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} weil q Wiederholungen nicht zulässig ist.

Jetzt meine schluchzende Geschichte: Ich bin ganz neu in der Codierung ... 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 Tupel Schlüssel wurden zwei Listen erzeugt werden: „ExpList1“ und „ExpList2“

#first, I generate all the tuple combinations from my ExpDict dictionary 
combos =(itertools.combinations(ExpDict,min(len(ExpList1),len(ExpList2)))) 

#then I generate a list of only the combinations that don't repeat p or q 
uniquecombolist = [] 
for foo in combos: 
    counter = 0 
    listofp = [] 
    listofq = [] 
    for bar in foo: 
     if bar[0] in listofp or bar[1] in listofq: 
      counter=+1 
      break 
     else: 
      listofp.append(bar[0]) 
      listofq.append(bar[1]) 
    if counter == 0: 
     uniquecombolist.append(foo) 

Nach dieser Liste zu erzeugen, habe ich eine Funktion, um alle die Anwendung Dictionary-Kombinationen (Iterieren durch die Tupel-Listen und Aufruf ihrer jeweiligen Werte aus dem Master-Dictionary) und wählen Sie die Kombination mit dem kleinsten resultierenden Wert aus dieser Funktion.

Ich habe auch versucht, die Funktion beim Iterieren durch die Kombinationen die eindeutigen p, q Einsen auszuwählen und dann zu überprüfen, ob der resultierende Wert kleiner ist als der vorherige und es behalten, wenn es ist (das ist, 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 p, q-No-Repeat und der endgültigen Auswahl-Funktion während der Generierung von Kombinationen. Ich habe nur Mühe, meinen Kopf darum zu wickeln, wie man das macht.

Danke fürs Lesen! Sara

EDIT:

Um zu klären, I eine Alternative zu meinen Code geschrieben, die die endgültige Funktion enthält (im Grunde root mean squares) auf die Sätze von Paaren.

`combos =(itertools.combinations(ExpDict,min(len(ExpList1),len(ExpList2)))) 


prevRMSD = float('inf') 
for foo in combos: 
    counter = 0 
    distanceSUM = 0 
    listofp = [] 
    listofq = [] 
    for bar in foo: 
     if bar[0] in listofp or bar[1] in listofq: 
      counter=+1 
      break 
     else: 
      listofp.append(bar[0]) 
      listofq.append(bar[1]) 
     distanceSUM = distanceSUM + RMSDdict[bar] 
    RMSD = math.sqrt (distanceSUM**2/len(foo)) 
    if counter == 0 and RMSD< prevRMSD: 
     chosencombo = foo 
     prevRMSD = RMSD` 

Also, wenn ich die RMS-Berechnung während der eingestellten Generation übernehmen könnte und halten nur die kleinste, denke ich, dass mein kombinatorisches Problem lösen.

Answer 1

Diese Antwort setzt voraus, dass Sie versuchen, Sätze mit | S | zu erzeugen Elemente, wobei S der kleinere Pool von Tupelkoordinaten ist. Der größere Pool wird mit L bezeichnet.

Da der Satz enthält | S | Paare mit nicht wiederholten Elementen, jedes Element von S muss genau einmal vorkommen. Passen Sie von hier aus die Permutationen von L mit | S | Elemente werden mit den geordneten Elementen von S ausgewählt. Dies erzeugt alle angeforderten Sätze erschöpfend und ohne Wiederholung.

Beachten Sie, dass P (| L |, | S |) gleich | L |!/(| L | - | S |) ist!

Je nach Größe der Tupelkoordinatenpools sind möglicherweise zu viele Permutationen vorhanden.

Einige Code, um diese Aufzählung replizieren könnte wie folgt aussehen:

from itertools import permutations 

S, L = range(2), range(4) # or ExpList1, ExpList2 
for p in permutations(L, len(S)): 
    print(zip(S, p)) 

Insgesamt Ihre endgültige Code könnte so etwas aussehen:

S, L = ExpList1, ExpList2 
pairset_maker = lambda p: zip(S, p) 

if len(S) > len(L): 
    S, L = L, S 
    pairset_maker = lambda p: zip(p, S) 

n = len(S) 
get_perm_value = lambda p: math.sqrt(sum(RMSDdict[t] for t in pairset_maker(p))**2/n) 

min_pairset = min(itertools.permutations(L, n), key=get_perm_value) 

Wenn dies bekommen Sie nicht innerhalb einer Bestellung oder eine oder zwei Größen Ihrer gewünschten Laufzeit, dann müssen Sie möglicherweise einen Algorithmus in Betracht ziehen, der keine optimale Lösung ergibt.

Answer 2

Wenn ich Ihr Problem verstanden habe, sind Sie an allen möglichen Kombinationen von Paaren (p, q) mit eindeutigen p's und qs interessiert, die einen gegebenen Satz möglicher Werte für p's und qs respektieren. In meiner Antwort nehme ich diese möglichen Werte sind jeweils in list_p und list_q (ich glaube, das ist, was haben Sie in ExpList1 und ExpList2 bin ich recht?)

min_size = min(len(list_p), len(list_q)) 

combos_p = itertools.combinations(list_p, min_size) 
combos_q = itertools.permutations(list_q, min_size) 
prod = itertools.product(combos_p, combos_q) 
uniquecombolist = [tuple(zip(i[0], i[1])) for i in prod] 

Lassen Sie mich wissen, ob dies ist, was du bist Auf der Suche nach. Übrigens Willkommen in SO, gute Frage!

---

Edit:

Wenn Sie besorgt, dass Ihre Liste enorm werden kann, können Sie immer einen Generator Ausdruck verwenden und anwenden, was Funktion, die Sie es wünschen, zum Beispiel

min_size = min(len(list_p), len(list_q)) 

combos_p = itertools.combinations(list_p, min_size) 
combos_q = itertools.permutations(list_q, min_size) 
prod = itertools.product(combos_p, combos_q) 
uniquecombo = (tuple(zip(y[0], y[1])) for y in prod) # this is now a generator expression, not a list -- observe the parentheses 

def your_function(x): 
    # do whatever you want with the values, here I'm just printing and returning 
    print(x) 
    return x 

# now prints the minimum value 
print(min(itertools.imap(your_function, uniquecombo))) 

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 handelt sich um das Minimum.