Het kroonjuweel in de collectie van de excentrieke museumdirecteur Idu Schurf is een zaal met vijftien Picasso's uit z'n blauwe periode. Schurf staat erom bekend dat hij zijn collectie permanent in beweging houdt, waartoe hij speciaal voor deze tentoonstelling een briljant instrument ontwikkeld heeft: de circadiale permutator. De haakjes waaraan de schilderijen hangen zijn genummerd van 1 tot en met 15, en boven elk haakje zit een briefje op de muur geplakt, waarop staat: "Hang dit schilderij op haakje …". Op de plaats van de puntjes staat een natuurlijk getal van 1 tot en met 15. Op de openingsdag van de tentoonstelling hangen de schilderijen in onderstaande volgorde. Hierbij staat boven elk schilderij telkens het getal tussen 1 en 15 dat op het briefje staat boven het haakje waaraan het schilderij hangt.
| 14 | 6 | 15 | 3 | 4 | 10 | 1 | 12 | 5 | 2 | 7 | 13 | 8 | 11 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
De suppoosten hebben de opdracht om iedere ochtend de Picasso's van hun haakje te halen en de opdracht op het briefje uit te voeren, zodat de bezoekers dagelijks tegen een opgefriste tentoonstelling aankijken. Op de tweede dag van de tentoonstelling hangen de schilderijen dus in onderstaande volgorde. Hierbij zie je bijvoorbeeld dat het schilderij dat op dag 1 aan haakje 7 hing, nu op dag 2 naar haakje 1 verplaatst werd.
| 14 | 6 | 15 | 3 | 4 | 10 | 1 | 12 | 5 | 2 | 7 | 13 | 8 | 11 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
De getallen werden door Schurf echter niet zomaar op de briefjes boven de haakjes van de schilderijen geplaatst. De directeur heeft ervoor gezorgd dat de tentoonstelling sluit op de laatste dag voordat alle schilderijen weer op dezelfde plaats zouden komen te hangen als tijdens de opening. Wat is de sluitingsdag? Had Schurf met een andere volgorde van de briefjes de tentoonstelling langer open kunnen houden, en zo ja, hoe lang? Hoe lang kan Schurf een tentoonstelling van $$n$$ Picasso's openhouden?
Opgave
We gaan bovenstaand probleem algemeen oplossen voor $$n$$ voorwerpen die volgens een gegeven permutatie van de getallen van 1 tot en met $$n$$ moeten verplaatst worden. Een permutatie van de getallen 1 tot en met $$n$$ is een lijst waarin elk getal tussen 1 en $$n$$ juist één keer voorkomt, zonder dat de volgorde van voorkomen daarbij van belang is. Bij het schrijven van onderstaande functies moet je er steeds voor zorgen dat de lijsten die je als argument aan de functie doorgeeft nooit gewijzigd worden.
-
Schrijf een functie isPermutatie die een Booleaanse waarde teruggeeft die aanduidt of een gegeven lijst van integers een permutatie van de getallen van 1 tot en met $$n$$ is of niet. Hierbij staat $$n$$ voor de lengte van de lijst. De gegeven lijst van integers moet als argument aan de functie doorgegeven worden.
-
Schrijf een functie permutator die volgens een gegeven permutatie een gegeven lijst van voorwerpen van plaats verwisselt. Als eerste argument moet aan deze functie een lijst doorgegeven worden die elk van de getallen van 1 tot en met $$n$$ juist één keer bevat. Deze lijst stelt de gegeven permutatie voor. Het tweede argument is een lijst van $$n$$ elementen, die de oorspronkelijke volgorde van de voorwerpen voorstelt. De functie moet een nieuwe lijst teruggeven die de nieuwe volgorde van de voorwerpen aangeeft, nadat die verplaatst werden volgens de gegeven permutatie. Je mag ervan uitgaan dat aan deze functie twee lijsten van gelijke lengte $$n$$ doorgegeven worden, en dat het eerste argument een permutatie van de getallen 1 tot en met $$n$$ bevat.
-
Gebruik de functies isPermutatie en permutator om een functie sluitingsdag te schrijven die bepaalt op welke dag de sluiting van een tentoonstelling valt, als de tentoongestelde voorwerpen elke dag gepermuteerd worden volgens een gegeven permutatie. De openingsdag wordt geteld als dag 1 van de tentoonstelling. Aan deze functie moet een lijst van $$n$$ getallen doorgegeven worden. De functie moet de waarde -1 teruggeven indien deze gegeven getallenlijst geen permutatie van de getallen 1 tot en met $$n$$ voorstelt. Anders moet de functie het dagnummer van de sluitingsdag als resultaat teruggeven.
Voorbeeld
>>> isPermutatie([2, 5, 3, 1, 6, 4])
True
>>> isPermutatie([1, 4, 2, 0, 5, 3])
False
>>> isPermutatie([2, 5, 3, 8, 1, 6, 4])
False
>>> briefjes = [3, 4, 1, 2]
>>> schilderijen = ['mona lisa', 'de schreeuw', 'het lam gods', 'de kus']
>>> schilderijen = permutator(briefjes, schilderijen)
>>> schilderijen
['het lam gods', 'de kus', 'mona lisa', 'de schreeuw']
>>> schilderijen = permutator(briefjes, schilderijen)
>>> schilderijen
['mona lisa', 'de schreeuw', 'het lam gods', 'de kus']
>>> briefjes = [14, 6, 15, 3, 4, 10, 1, 12, 5, 2, 7, 13, 8, 11, 9]
>>> schilderijen = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
>>> schilderijen = permutator(briefjes, schilderijen)
>>> schilderijen
[7, 10, 4, 5, 9, 2, 11, 13, 15, 6, 14, 8, 12, 1, 3]
>>> schilderijen = permutator(briefjes, schilderijen)
>>> schilderijen
[11, 6, 5, 9, 15, 10, 14, 12, 3, 2, 1, 13, 8, 7, 4]
>>> schilderijen = permutator(briefjes, schilderijen)
>>> schilderijen
[14, 2, 9, 15, 3, 6, 1, 8, 4, 10, 7, 12, 13, 11, 5]
>>> briefjes = [3, 4, 1, 2]
>>> sluitingsdag(briefjes)
2
>>> briefjes = [14, 6, 15, 3, 4, 10, 1, 12, 5, 2, 7, 13, 8, 11, 9]
>>> sluitingsdag(briefjes)
60