PROG0283 - Circadial permutator
The crown jewel in the collection of the eccentric museum director Idu Schurf is a room with fifteen paintings of Picasso from his blue period. Schurf has a reputation that he keeps his collection under constant movement. For his next exhibition he has has developed an extraordinary tool: the circadial permutator. The clamps that hold the paintings have been labeled 1 to 15, and on top of each clamp there is a note on the wall that says: "Move this painting to clamp …". The ellipsis are used here as a placeholder for an integer between 1 and 15. On the opening day of the exhibition, the paintings are displayed in the order as shown below. On top of each painting we show the integer that is on the note above the clamp to which the painting is attached.
| 14 | 6 | 15 | 3 | 4 | 10 | 1 | 12 | 5 | 2 | 7 | 13 | 8 | 11 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
The attendants have been given the job to remove the Picasso paintings every morning and carry out the task that is on the note. As such, the visitors of the museum can look at a refreshed exhibition on each successive day. On the second day of the exhibition, the paintings are displayed in the order as shown below. In this example you can see that the painting that was at clamp 7 on the first day, has been moved to clamp 1 on the second day.
| 14 | 6 | 15 | 3 | 4 | 10 | 1 | 12 | 5 | 2 | 7 | 13 | 8 | 11 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
|
|
|
|
|
|
|
|
|
|
|
|
à
|
|
|
However, Schurf has not just randomly written some numbers on the notes above the clamps of the paintings. The director has organised them in such a way to ensure that the exhibition closes on the last day before all paintings are back on their original position as during the opening day. Can you compute how many days the exhibition lasts? Could Schurf have rearranged the numbers to keep the exhibition running a bit longer, and if so, how long? How long can Schurf hold an exhibition of $n$ Picasso paintings?
Assignment
We are going to solve a generalized version of the above problem, in which $n$ objects are rearranged according to a given permutation of the integers from 1 up to and including $n$. A permutation of the integers from 1 up to and including $n$ is a list that contains each integer from 1 up to and including $n$ just once. The order in which the integers occur is of no importance. When writing the functions described below, you need to make sure that any list passed as an argument to a functions is never modified by the function.
- Write a function ispermutation that returns a Boolean indicating whether or not a given list of integers is a permutation of the integers from 1 up to an including $n$, where $n$ is the length of the list. The given list of integers must be passed as an argument to the function.
- Write a function permutator that rearranges the objects in a list according to a given permutation. The first argument passed to the function must be a list that contains each integer from 1 up to and including $n$ just once. This list represents the given permutation. The second argument is a list of $n$ elements, that gives the original order of the objects. The function must return a new list holding the new order of the objects, after having them rearranged according to the given permutation. You may assume that both lists passed to the function have an equal length $n$, and that the first argument is a permutation of the integers from 1 up to and including $n$.
- Use the functions ispermutation and permutator to write a function closingday that determines on what day an exhibition closes if the exhibits are permuted on a daily basis according to a given permutation. The opening day is considered to be day 1 of the exhibition. A list of $n$ integers must be passed as an argument to the function. The function must return the value -1 if the numbers in the list do not constitute a permutation of the integers from 1 up to and including $n$. Otherwise, the function must return the number of the day after which the exhibition closes its doors.
Example
>>> ispermutation([2, 5, 3, 1, 6, 4]) True >>> ispermutation([1, 4, 2, 0, 5, 3]) False >>> ispermutation([2, 5, 3, 8, 1, 6, 4]) False >>> notes = [3, 4, 1, 2] >>> paintings = ['mona lisa', 'the scream', 'ghent altarpiece', 'the kiss'] >>> paintings = permutator(notes, paintings) >>> paintings ['ghent altarpiece', 'the kiss', 'mona lisa', 'the scream'] >>> paintings = permutator(notes, paintings) >>> paintings ['mona lisa', 'the scream', 'ghent altarpiece', 'the kiss'] >>> notes = [14, 6, 15, 3, 4, 10, 1, 12, 5, 2, 7, 13, 8, 11, 9] >>> paintings = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15] >>> paintings = permutator(notes, paintings) >>> paintings [7, 10, 4, 5, 9, 2, 11, 13, 15, 6, 14, 8, 12, 1, 3] >>> paintings = permutator(notes, paintings) >>> paintings [11, 6, 5, 9, 15, 10, 14, 12, 3, 2, 1, 13, 8, 7, 4] >>> paintings = permutator(notes, paintings) >>> paintings [14, 2, 9, 15, 3, 6, 1, 8, 4, 10, 7, 12, 13, 11, 5] >>> notes = [3, 4, 1, 2] >>> closingday(notes) 2 >>> notes = [14, 6, 15, 3, 4, 10, 1, 12, 5, 2, 7, 13, 8, 11, 9] >>> closingday(notes)
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
| Added by: | Peter Dawyndt |
| Date: | 2012-09-08 |
| Time limit: | 5s-10s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | PY_NBC |
| Resource: | None |
RSS