In de kansrekening komen dikwijls urneproblemen aan bod. Hierbij worden 1 of meerdere urnen gevuld met objecten, en vervolgens worden uit die urnen een aantal objecten blind gekozen, al dan niet met terugleggen. Het probleem bestaat er dan in te bepalen wat de kans is om een bepaalde configuratie van objecten te kiezen. Een voorbeeld van een dergelijk urneprobleem luidt: een urne is gevuld met 3 rode en 6 witte ballen. Wat is de kans om als je hier 2 balletjes uit kiest (zonder terugleggen), dat deze balletjes een verschillende kleur hebben?

In deze oefening programmeren we een basisklasse UrneProbleem die in staat is heel wat functionaliteit te realiseren om dergelijke kansen via simulatie te bepalen. In deze klasse voorzien we gegevens en logica om de inhoud van de urnen vast te leggen en om objecten uit de urnen (al dan niet met terugleggen) te kiezen. Daarnaast bevat ze ook de logica om een reeks experimenten te laten uitvoeren, en de kansberekening uit te voeren, zonder concreet de logica van het experiment zelf te bevatten. Alle informatie over een concreet experiment wordt gelokaliseerd in klassen die overerven van de klasse UrneProbleem.

De klasse UrneProbleem

Voorzie het volgende in deze klasse:

• een constructor met als argument de initiële inhoud van de urnes. Elke urne wordt voorgesteld door een lijst van strings, en het argument van de constructor is dus een lijst van lijsten van strings. Lege urnes worden hierbij genegeerd (m.a.w. mocht een lijst die een urne voorstelt leeg zijn, dan negeer je deze).

• de methode __str__(): deze methode levert de standaard string-gedaante van de lijst-van-lijsten die de huidige inhoud van de urnen voorstelt (deze kan natuurlijk verschillend zijn van de originele inhoud van de urnen).

• de methode kies_met_terugleggen() : hierbij wordt een willekeurig object uit een willekeurige urne gekozen, waarna het object teruggelegd wordt (de urnen blijven dus qua inhoud ongewijzigd). Hierbij ga je als volgt tewerk:

  • bepaal via random.randint() een willekeurige urne (m.a.w. de index $$i_u$$ van de urne in de lijst-van-lijsten die de urnes voorstellen)
  • bepaal via random.randint() een willekeurig element in die gekozen urne (m.a.w. de index $$i_o$$ in de lijst die de gekozen urne voorstelt)
  • het resultaat van de methode is een tuple met drie elementen $$(i_u, i_o, element)$$

• de methode kies_zonder_terugleggen() : identieke werking als de methode met terugleggen, alleen wordt het gekozen element uit de urne verwijderd. Indien hierdoor de urne leeg wordt, verwijder je ook deze urne.

• de methode bereken_kans() met als enig argument het aantal uit te voeren experimenten $$N \gt 0$$. In elk van de $$N$$ iteraties onderneem je volgende acties:

  • vul de urnen opnieuw met hun originele inhoud
  • roep de methode self.doe_experiment() op (merk op: de methode doe_experiment() wordt NIET in de klasse UrneProbleem geprogrameerd maar wel in klassen die hiervan overerven). Deze methode levert de waarde True op indien het experiment succesvol is en de waarde False in het andere geval.
  Het resultaat van de methode is de fractie succesvolle experimenten (die dus een benadering van de gezochte kans voorstelt).

De klasse GekleurdExperimentMetTerugleggen

De urnen worden hier gevuld met objecten van verschillende soorten (b.v. een aantal rode en witte balletjes). We kiezen een aantal objecten uit deze urnen (logica van kiezen zoals hierboven beschreven), met terugleggen. In deze klasse realiseren we de logica om uit de urnen een aantal objecten te kiezen met terugleggen, en na te gaan hoeveel objecten van elke soort er gekozen werden. Programmeer in deze klasse, die overerft van de klasse UrneProbleem:

• een constructor met als argumenten:

  • een lijst-van-lijsten die de initiële urneinhoud voorstellen (die klasse UrneProbleem)
  • een natuurlijke getal (int) strikt groter dan 0, dat het aantal te kiezen objecten aangeeft
  • een woordenboek dat het gewenst resultaat aangeeft opdat een experiment succesvol zou zijn. Hierbij stellen de sleutels de soorten objecten voor (type string) en de waarden het gewenste aantal.

• de methode doe_experiment() zonder argumenten, kiest het opgegeven aantal objecten uit de urnes, met terugleggen, en kijkt na of van elke soort het gewenste aantal gekozen werd. Is dit het geval, dan is het resultaat van de methode True. In het andere geval is het resultaat van de methode False.

De klasse GekleurdExperimentZonderTerugleggen

Deze klasse is vrijwel identiek aan de vorige (en erft dus best over van de klasse GekleurdExperimentMetTerugleggen. Het enige verschil is dat objecten nu NIET teruggelegd worden.

LET OP: verander de seed niet, en gebruik ook de randomgenerator enkel zoals hierboven aangegeven (anders is het resultaat niet controleerbaar via Dodona).

Voorbeeld

random.seed(100)
u0 = ['rood']*2 + ['groen']*3 + ['blauw']
u1 = ['rood']*3 + ['blauw']*2
p0 = UrneProbleem([u0, [], u1])
print(p0)
# [['rood', 'rood', 'groen', 'groen', 'groen', 'blauw'], ['rood', 'rood', 'rood', 'blauw', 'blauw']]
print(p0.kies_met_terugleggen()) #(0, 3, 'groen')
print(p0.kies_zonder_terugleggen()) #(1, 1, 'rood')
print(p0)
#[['rood', 'rood', 'groen', 'groen', 'groen', 'blauw'], ['rood', 'rood', 'blauw', 'blauw']]

u = ['rood']*3 + ['wit']*3
p1 = GekleurdExperimentMetTerugleggen([u], 1, {'rood':1, 'wit':0})
print(p1.bereken_kans(10)) #0.6
p2 = GekleurdExperimentMetTerugleggen([u], 2, {'rood':2, 'wit':0})
print(p2.bereken_kans(1000)) #0.266
p3 = GekleurdExperimentZonderTerugleggen([u], 2, {'rood':2, 'wit':0})
print(p3.bereken_kans(10000)) #0.2023