Naar jaarlijkse gewoonte scharen de gezinnen van een familie zich rond het haardvuur om Kerstmis te vieren. Op het hoogtepunt van de avond deelt elk familielid een geschenk uit aan een andere familielid, waarbij iedereen één geschenk uitdeelt en iedereen één geschenk ontvangt. Om dat te organiseren, worden er een paar weken voorafgaand aan de festiviteiten kaartjes met alle namen van de familieleden in een grote hoed gestopt en mag iedereen blind één kaartje uit de hoed trekken. Als iemand toevallig zijn eigen naam zou trekken, dan gaan alle kaartjes terug in de hoed, en wordt de procedure herhaald totdat iedereen iemand anders getrokken heeft. Omdat iedereen dit jaar toevallig een kaartje getrokken heeft waarop de naam van iemand van zijn of haar eigen gezin staat, heeft de familie afgesproken om de volgende trekking te blijven herhalen totdat niemand een kaartje getrokken heeft van een eigen gezinslid.

Voorbereiding

In de module random wordt een functie shuffle gedefinieerd die de elementen van een gegeven lijst willekeurig door elkaar schudt. Onderstaande sessie illustreert de werking van deze functie. Merk dus op dat de functie shuffle geen nieuwe lijst teruggeeft, maar de elementen in place van plaats verwisselt.

>>> from random import shuffle

>>> lijst = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
>>> shuffle(lijst)
>>> lijst
[2, 7, 8, 9, 3, 6, 1, 5, 4, 10]
>>> shuffle(lijst)
>>> lijst
[8, 10, 6, 7, 4, 2, 9, 3, 5, 1]

Opgave

In deze opgave stellen we een gezin voor als een (bevroren) verzameling van strings, waarbij de strings de namen van de gezinsleden bevatten. Een samenstelling van een familie wordt voorgesteld als een lijst, een tuple of een verzameling van gezinnen. Hierbij mag verondersteld worden dat een familie uit minstens twee gezinnen bestaat, en dat er binnen een familie geen twee personen zijn die dezelfde naam hebben. Voor een gegeven familie wordt een trekking voorgesteld als een dictionary die de namen van alle familieleden één-op-één afbeeldt op de namen van alle familieleden. De naam van elk familielid komt dus juist één keer als sleutel en juist één keer als waarde voor in de dictionary. Deze afbeelding stelt dus voor wie (sleutel in dictionary) een geschenk moet uitdelen aan wie (waarde die correspondeert met sleutel).

• Schrijf een functie isGeldigeTrekking waaraan twee argumenten moeten doorgegeven worden: een trekking en de samenstelling van de familie waarvoor de trekking gebeurd is. De functie moet een Booleaanse waarde teruggeven die aangeeft of de trekking al of niet geldig is. Hierbij mag de functie ervan uitgaan dat de gegeven trekking een één-op-één afbeelding van de namen van de familieleden voorstelt. De functie moet echter wel nagaan of geen enkel familielid aan zichzelf een geschenk zou moeten uitdelen (wat de trekking ongeldig maakt). De functie heeft ook nog een derde optionele parameter zelfdeGezin (standaardwaarde: False), die aangeeft of de functie bijkomend moet nagaan of geen enkel familielid een geschenk zou moeten uitdelen aan iemand van zijn of haar eigen gezin (wat de trekking ongeldig maakt).

• Schrijf een functie maakTrekking waaraan de samenstelling van een familie moet doorgegeven worden. De functie moet een dictionary teruggeven, die een trekking voor de gegeven familie voorstelt. Merk op dat hiervoor dus niet moet gelden dat de trekking geldig is volgens de functie isGeldigeTrekking, met andere woorden dat iedereen aan iemand anders een geschenk moet uitdelen of dat gezinsleden niet aan elkaar een geschenk mogen uitdelen. Deze voorwaarden zullen pas opgelegd worden aan de functie die hierna wordt beschreven.

• Gebruik de functies isGeldigeTrekking en maakTrekking om een functie maakGeldigeTrekking te schrijven, waaraan de samenstelling van een familie moet doorgegeven worden. De functie heeft ook nog een tweede optionele parameter zelfdeGezin (standaardwaarde: False), die dezelfde betekenis heeft als bij de functie isGeldigeTrekking. De functie moet een dictionary teruggeven, die een geldige trekking teruggeeft in de betekenis zoals vastgelegd voor de functie isGeldigeTrekking.

Voorbeeld

>>> familie = ({'Alice', 'Bob', 'Cindy'}, {'Dora', 'Eric', 'Felix'})

>>> trekking = {
...   'Alice': 'Bob', 
...   'Cindy': 'Dora', 
...   'Dora': 'Alice', 
...   'Eric': 'Eric', 
...   'Bob': 'Felix', 
...   'Felix': 'Cindy'
... }
>>> isGeldigeTrekking(trekking, familie)
False

>>> trekking = {
...   'Alice': 'Dora', 
...   'Cindy': 'Felix', 
...   'Dora': 'Eric', 
...   'Eric': 'Cindy', 
...   'Bob': 'Alice', 
...   'Felix': 'Bob'
... }
>>> isGeldigeTrekking(trekking, familie)
True
>>> isGeldigeTrekking(trekking, familie, zelfdeGezin=True)
False

>>> trekking = {
...   'Alice': 'Dora', 
...   'Cindy': 'Eric', 
...   'Dora': 'Alice', 
...   'Eric': 'Bob', 
...   'Bob': 'Felix', 
...   'Felix': 'Cindy'
... }
>>> isGeldigeTrekking(trekking, familie)
True
>>> isGeldigeTrekking(trekking, familie, zelfdeGezin=True)
True

>>> maakTrekking(familie)
{
	'Alice': 'Cindy', 
	'Cindy': 'Alice', 
	'Dora': 'Bob', 
	'Eric': 'Dora', 
	'Bob': 'Felix', 
	'Felix': 'Eric'
}

>>> maakGeldigeTrekking(familie)
{
	'Alice': 'Cindy', 
	'Cindy': 'Bob', 
	'Dora': 'Alice', 
	'Eric': 'Felix', 
	'Bob': 'Eric', 
	'Felix': 'Dora'
}
>>> maakGeldigeTrekking(familie, zelfdeGezin=True)
{
	'Alice': 'Felix', 
	'Cindy': 'Eric', 
	'Dora': 'Bob', 
	'Eric': 'Alice', 
	'Bob': 'Dora', 
	'Felix': 'Cindy'
}