Een groep van $$N$$ studenten zoekt een stageplaats bij $$N$$ bedrijven (elk bedrijf biedt dus 1 stageplaats aan, en gelukkig zijn er evenveel stageplaatsen als er studenten zijn). Om stageplaatsen op een zinvolle manier toe te kennen, geven studenten hun voorkeur voor bedrijven aan, en omgekeerd geven ook bedrijven hun voorkeur aan voor studenten. Deze voorkeur wordt voorgesteld door een natuurlijk getal, nl. tussen 1 en N (grenzen inbegrepen). De hoogste voorkeur krijgt hierbij 1, de laagste voorkeur wordt door het getal N voorgesteld.

De studenten worden in een lijst geordend (en krijgen dus een rangnummer tussen 0 en N-1 (grenzen inbegrepen)), en analoog worden de bedrijven via een lijst geordend (en elk bedrijf krijgt dus ook een rangnummer tussen 0 en N-1 (grenzen inbegrepen)). De voorkeur van de studenten wordt weergegeven in een lijst $$s$$ van $$N$$ lijsten, met elk $$N$$ gehele getallen (elk getal 1 t.e.m. N komt voor, er zijn geen ex aequo's), en analoog voor de voorkeur van de bedrijven, voorgesteld door de lijst $$b$$. Op die manier geeft de variabele $$s[i][j]$$ de voorkeur van student $$i$$ aan voor bedrijf $$j$$, en geeft de variabele $$b[i][j]$$ de voorkeur aan van bedrijf $$i$$ voor student $$j$$.

Een toekenning van studenten aan bedrijven, zullen we voorstellen via een woordenboek $$w$$. De sleutel in dit woordenboek is een rangnummer van een bedrijf (dus een natuurlijk getal tussen 0 en N-1 (grenzen inbegrepen)) en de bijhorende waarde is het rangnummer van de toegewezen student (opnieuw een natuurlijk getal tussen 0 en N-1 (grenzen inbegrepen)).

Klasse StageBeheer

Programmeer in deze klasse het volgende:

• een constructor met 2 argumenten, namelijk de lijsten $$s$$ en $$b$$ zoals hierboven gedefinieerd
• de methode geldige_toekenning() met als enig argument een woordenboek, dat een toekenning (zie hoger) voorstelt. De methode geeft True of False terug, naargelang het om een geldige toekenning gaat. Een toekenning is hierbij geldig indien tegelijk voldaan is aan onderstaande voorwaarden:
  • Elk bedrijf krijgt precies 1 student als stagiair toegewezen
  • Elke student heeft precies 1 bedrijf waar hij/zij stage kan lopen
• de methode beste_bedrijf() heeft 1 argument, een natuurlijk getal, dat een rangnummer van een student voorstelt. Het resultaat van de methode is het rangnummer van beste bedrijf voor die student. Je mag aannemen dat het argument een geldige waarde aanneemt.
• de methode beste_student() heeft 1 argument, een natuurlijk getal, dat een rangnummer van een bedrijr voorstelt. Het resultaat van de methode is het rangnummer van beste student voor dit bedrijf. Je mag aannemen dat het argument een geldige waarde aanneemt.
• de methode score_toekenning_bedrijf() heeft als enig argument een woordenboek dat een toekenning voorstelt. De methode levert als resultaat een geheel getal, namelijk:
  • de waarde -1 indien de toekenning niet geldig is (zie hoger)
  • de som van de voorkeuren van bedrijven voor toegewezen studenten (voor elk bedrijf ga je dus de voorkeur na voor de student die toegewezen werd, en je sommeert die waarde). Hoe lager deze score, hoe beter dus de toekenning vanuit het oogpunt van het bedrijf.
• de methode score_toekenning_student() vertoont een gelijkaardig gedrag, alleen wordt nu gesommeerd over de voorkeuren van elke student voor het bedrijf dat hem/haar toegewezen werd (let erop dat het argument nog steeds een woordenboek is dat bedrijfrangnummers afbeeldt op studentrangnummers).
• de methode zoek_toekenning() heeft 1 object als argument, en dit object beschikt over een methode toekenning(). Deze methode heeft 1 argument, namelijk een object van de klasse stageBeheer waarvoor een toekenning moet bepaald worden, via een welbepaalde strategie (zie verder). Het resultaat van de methode toekenning() is een woordenboek dat een gevonden toekenning voorstelt.

Voorbeeld

sb = StageBeheer([[4, 5, 2, 1, 3], [2, 1, 5, 3, 4], [5, 2, 4, 1, 3], [1, 5, 3, 4, 2], [4, 3, 1, 2, 5]], [[3, 5, 1, 4, 2], [3, 5, 1, 4, 2], [4, 3, 5, 2, 1], [4, 5, 3, 1, 2], [1, 4, 2, 5, 3]])
print(sb.beste_bedrijf(3)) #0
print(sb.beste_bedrijf(2)) #3
print(sb.beste_student(2)) #4
print(sb.beste_student(4)) #0
print(sb.geldige_toekenning({0: 0, 1: 3, 2: 4, 3: 2, 4: 1})) #True
print(sb.geldige_toekenning({0: 6, 1: 3, 2: 4, 3: 0})) #False
print(sb.score_toekenning_bedrijf({0: 0, 1: 3, 2: 4, 3: 2, 4: 1})) #15
print(sb.score_toekenning_bedrijf({0: 6, 1: 3, 2: 4, 3: 0})) #-1
print(sb.score_toekenning_student({0: 0, 1: 3, 2: 4, 3: 2, 4: 1})) #15
print(sb.score_toekenning_student({0: 6, 1: 3, 2: 4, 3: 0})) #-1

Elk van onderstaande klassen beschikt over de methode toekenning() met als enig argument een object van de klasse stageBeheer. Het resultaat van de methode is een woordenboek dat een gevonden toekenning voorstelt. De tekst hieronder beschrijft telkens de te volgen strategie bij het genereren van oplossingen voor het toekenningsprobleem.

Klasse DefaultZoeker

Het resultaat komt tot stand door aan het bedrijf met rangnummer $$i$$ student met rangnummer $$i$$ toe te kennen.

Klasse GulzigBedrijfZoeker

Loop alle bedrijven af in de volgorde waarin ze in de lijst van voorkeuren voorkomen. Kies voor elk bedrijf de meest geschikte student, die nog geen bedrijf toegewezen kreeg.

Klasse GulzigStudentZoeker

Loop alle studenten af in de volgorde waarin ze in de lijst van voorkeuren voorkomen. Koppel aan elke student het meest geschikte bedrijf, dat nog geen stagiair toegewezen kreeg.

Voorbeeld

sb = StageBeheer([[6, 3, 2, 5, 4, 1], [2, 4, 5, 1, 3, 6], [4, 2, 6, 3, 1, 5], [2, 3, 5, 6, 1, 4], [1, 2, 3, 5, 4, 6], [3, 1, 2, 6, 4, 5]], [[2, 4, 3, 5, 1, 6], [1, 2, 5, 3, 4, 6], [5, 1, 2, 6, 3, 4], [6, 2, 1, 5, 4, 3], [4, 5, 2, 1, 6, 3], [6, 4, 3, 1, 5, 2]])
sb.zoek_toekenning(DefaultZoeker()) #{0: 0, 1: 1, 2: 2, 3: 3, 4: 4, 5: 5}
sb.zoek_toekenning(GulzigBedrijfZoeker()) #{0: 4, 1: 0, 2: 1, 3: 2, 4: 3, 5: 5}
sb.zoek_toekenning(GulzigStudentZoeker()) #{0: 3, 1: 4, 2: 5, 3: 1, 4: 2, 5: 0}

Klasse StabieleToekenningZoeker

• Hou voor elk bedrijf bij aan welke student al een voorstel tot stage werd gedaan (voorstellen kunnen tijdelijk geweigerd worden). Initieel is er dus door geen enkel bedrijf een voorstel gedaan.
• Zoek het bedrijf $$b$$ met laagste rangnummer dat nog geen stagiair heeft. Indien zo'n bedrijf niet kan gevonden worden, stopt het algoritme.
• Bekijk voor dit bedrijf $$b$$ alle studenten die nog geen voorstel ontvingen van dit bedrijf. Rangschik deze studenten volgens de voorkeur van het bedrijf voor die studenten. Noem $$s$$ de student die eerst in die lijst voorkomt. Hou bij dat student $$s$$ van bedrijf $$b$$ een voorstel ontving.
  • Indien student $$s$$ nog geen stageplaats toegewezen kreeg, koppel je (voorlopig) de student $$s$$ aan dit bedrijf $$b$$
  • Indien student $$s$$ wel aan een ander bedrijf $$b'$$ gekoppeld werd:
    • Indien bedrijf $$b'$$ de voorkeur van student $$s$$ geniet, blijft de toekenning van $$s$$ aan $$b'$$ geldig
    • Indien bedrijf $$b$$ de voorkeur van de student $$s$$ geniet, wordt deze nieuwe betere koppeling gemaakt
• Herhaal vanaf de 2de stap tot de toekenning geldig is (en elk bedrijf dus een stagiair heeft).

Voorbeeld

sb = StageBeheer([[3, 2, 4, 1], [4, 2, 3, 1], [4, 3, 2, 1], [3, 2, 4, 1]], [[1, 3, 4, 2], [2, 3, 4, 1], [1, 3, 2, 4], [2, 1, 3, 4]])
sb.zoek_toekenning(StabieleToekenningZoeker()) #{0: 0, 1: 3, 2: 2, 3: 1}