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