Untitled
def gale_shapley_algorithmus (studis, plätze): matches = {} # hier aktuellen Matchs speichern freie_studis = list(studis.keys()) # liste-> freie Studierende freie_plätze = {platz: None for platz in plätze} # am Anfang zunächst jeder Platz frei # Weisen jedem Studierenden ein Pointer auf seine noch nicht angefragten Plätze zu studis_präferenzen = {stud: list(prefs) for stud, prefs in studis.items()} platz_präferenzen = {platz: list(prefs) for platz, prefs in plätze.items()} iteration = 0 while freie_studis: iteration += 1 # Nummer der Iteration print(f"Iteration {iteration}") # returned die Iterationsnummer # Gehe durch die freien Studierenden in alphabetischer Reihenfolge for stud in sorted(freie_studis): # Alphabetische Reihenfolge der Studierenden # Studierender macht ein Angebot an den ersten freien Platz in seiner Liste angebotener_platz = studis_präferenzen[stud].pop(0) print(f"Studierender {stud} (i) bietet Praktikumsplatz {angebotener_platz} (j) an.") # wahl von i & j if freie_plätze[angebotener_platz] is None: # Angabe ob j aktuell frei oder nicht matches[stud] = angebotener_platz # Angabe eines neu gebildeten Matches freie_studis.remove(stud) print(f"Praktikumsplatz {angebotener_platz} (j) ist jetzt besetzt mit Studierendem {stud} (i).") else: # Platz ist schon besetzt, prüfen, ob der neue Studierende bevorzugt wird aktueller_match = freie_plätze[angebotener_platz] if platz_präferenzen[angebotener_platz].index(stud) < platz_präferenzen[angebotener_platz].index(aktueller_match): # wenn j nicht frei ist, angabe wer präferiert wird # Der Platz bevorzugt den neuen Studierenden # Studierender wird akzeptiert, der alte wird abgelehnt matches[stud] = angebotener_platz matches.pop(aktueller_match) freie_studis.remove(stud) freie_studis.append(aktueller_match) print(f"Praktikumsplatz {angebotener_platz} (j) bevorzugt Studierenden {stud} (i) gegenüber {aktueller_match} (i).") else: # Angabe, falls j i zurückweist print(f"Praktikumsplatz {angebotener_platz} (j) lehnt Studierenden {stud} (i) ab.") # freie_studis_sorted = sorted(freie_studis) # Angabe aller aktuell freien Elemente beider Seiten freie_plätze_sorted = [platz for platz, match in freie_plätze.items() if match is None] print(f"Frei sind: {', '.join(freie_studis_sorted)} und {', '.join(freie_plätze_sorted)}") print(f"Aktuelle Matches: {matches}") # Angabe aller aktuellen Matches am Ende einer Iteration print() return matches studis = { # Beispiel Daten (Präferenzlisten für Studierende und Praktikumsplätze) 'S1': ['P1', 'P2', 'P3', 'P4'], 'S2': ['P4', 'P1', 'P2', 'P3'], 'S3': ['P1', 'P4', 'P3', 'P2'], 'S4': ['P2', 'P4', 'P3', 'P1'] } plätze = { 'P1': ['S2', 'S4', 'S3', 'S1'], 'P2': ['S2', 'S1', 'S4', 'S3'], 'P3': ['S4', 'S2', 'S1', 'S3'], 'P4': ['S4', 'S1', 'S3', 'S2'] } matches = gale_shapley_algorithm(studis, plätze) # gale-Shapley-Algorithmus ausführen print("Endgültige Zuordnungen:", matches) # Endergebnis: Zeige finale Zuordnungen
Leave a Comment