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)