Two words form an anagram if one word can be formed by rearranging the letters of the other word. This works in both directions. However, we will consider an anagram to be a pair of words with a fixed order and view the second word as a rearrangement of the letters of the first word, for example, CESAROLITE → ESOTERICAL.
If the words consist of $$n$$ letters, we number the letters in the first word from 0 to $$n - 1$$. We can then describe a rearrangement of the letters as a permutation of their positions. For example, we can describe the anagram CESAROLITE → ESOTERICAL with $$n = 10$$ letters as the permutation (1, 2, 5, 8, 9, 4, 7, 0, 3, 6): the first letter of ESOTERICAL appears at position 1 in CESAROLITE, the second letter at position 2, the third letter at position 5, the fourth letter at position 8, …, and the last letter at position 6. We can also render the rearrangement by writing the letters of the first word around a circle and connecting the consecutive positions from the permutation, also connecting the last position with the first position.
This permutation connects the neighboring letters ES and TE (orange connections). Star anagrams are a special class of anagrams in which the letters have been maximally shuffled: no letter in the second word retains any of its original neighbors in the first word, counting the first and last letters as neighbors.
Because the letter E appears twice in the word CESAROLITE, there is a second permutation to describe the anagram CESAROLITE → ESOTERICAL: (9, 2, 5, 8, 1, 4, 7, 0, 3, 6). If we render this permutation, the result is a perfect ten-pointed star.
Jason Parker and Dan Barker systematically searched for perfect star anagrams among all English words, and this is the largest one they found. Only 5.7 percent of all anagrams in English turned out to be maximally shuffled, and even those anagrams rarely produce a perfect star.
Assignment
We search for perfect star anagrams of words (str) consisting solely of uppercase letters.
We represent a permutation describing an $$n$$-letter anagram as a tuple $$(p_0, p_1, \ldots, p_{n-1})$$, where $$p_i $$ (int; $$i = 0, 1, \ldots, n - 1$$) are the numbers 0 through $$n - 1$$ in random order.
To determine whether a permutation $$(p_0, p_1, \ldots, p_{n-1})$$ represents a (perfect) star, we determine a tuple $$(s_0, s_1, \ldots, s_{n-1})$$ with steps $$s_i$$ (int; $$i = 0, 1, \ldots, n - 1$$). For simplicity, let us assume that $$p_n \equiv p_0$$ (after the last position in the permutation follows the first position). The steps are then calculated as \[ s_i = (p_{i+1} - p_i)\!\!\!\!\mod{n} \] which expresses that $$s_i$$ represents the number of steps we must take clockwise around the circle to go from position $$p_i$$ to position $$p_{i+1}$$ — two consecutive positions from the permutation that are connected to each other. The operator $$a\!\!\!\mod{b}$$ represents the remainder upon integer division (the quotient) of $$a \in \mathbb{N}$$ by $$b \in \mathbb{N}_0$$ (modulo operation). For the anagram DOWNLOAD → WOODLAND with $$n = 8$$ letters, we get
| permutation | 2 | 5 | 1 | 7 | 4 | 6 | 3 | 0 |
| steps | 3 | 4 | 6 | 5 | 2 | 5 | 5 | 2 |
A permutation $$(p_0, p_1, \ldots, p_{n-1})$$ is a star if the numbers $$1$$ and $$n - 1$$ do not appear in the tuple with steps for the permutation. After all, if a permutation takes $$1$$ step, a letter around the circle is connected with its immediate neighbor in a clockwise direction. If a permutation takes $$n - 1$$ steps, a letter is connected with its immediate neighbor in a counterclockwise direction.
A permutation $$(p_0, p_1, \ldots, p_{n-1})$$ is perfect if all numbers in the tuple with steps for the permutation are equal. If all steps are equal, then all connecting lines are of equal length.
The above permutation describing the anagram DOWNLOAD → WOODLAND is therefore a star but not perfect.
We use the anagram DOWNLOAD → WOODLAND also to explain how to find all permutations that describe an anagram. First, we number the positions of the letters of the first word (DOWNLOAD) starting from zero. Then we start with a set that only contains the empty tuple. For each letter of the second word (WOODLAND), we systematically extend all tuples in the set with all possible positions where that letter occurs in the first word. However, a tuple is only extended with a position if that position did not already appear in the tuple.
The first letter (W) of WOODLAND only occurs at position 2 in DOWNLOAD, so we extend the empty tuple to tuple (2), because position 2 obviously did not yet appear in the empty tuple. The second letter (O) of WOODLAND occurs at positions 1 and 5 of DOWNLOAD, so we extend tuple (2) to the tuples (2, 1) and (2, 5) because both position 1 and position 5 did not yet appear in tuple (2). The third letter (O) of WOODLAND occurs at positions 1 and 5 of DOWNLOAD. We therefore extend tuple (2, 1) to tuple (2, 1, 5), but not to tuple (2, 1, 1) because position 1 already appears in tuple (2, 1). Similarly, we extend tuple (2, 5) to tuple (2, 5, 1), but not to tuple (2, 5, 5) because position 5 already appears in the tuple (2, 5). Above you can see how we further extend the set of tuples with the remaining letters of WOODLAND to finally obtain a set of four permutations that describe the anagram DOWNLOAD → WOODLAND.
We say that an anagram is a star if it is described by at least one star permutation. We say that an anagram is a perfect star if it is described by at least one star permutation that is also perfect.
Your task:
-
Write a function steps that takes a permutation (tuple). The function must return the tuple with steps (int) for the permutation.
-
Write a function isstar_permutation that takes a permutation (tuple). The function must return a Boolean value (bool) indicating whether the permutation is a star.
-
Write a function isperfect_permutation that takes a permutation (tuple). The function must return a Boolean value (bool) indicating whether the permutation is perfect.
-
Write a function positions that takes a word (str). The function must return a dictionary (dict) that maps each letter (str) in the word onto a set containing all positions (int) where that letter occurs in the word. The positions of the letters are numbered from left to right, starting from zero.
-
Write a function extend that takes two arguments: i) a set containing tuples (tuple) with positions (int), and ii) a set containing positions (int). The function must return a new set containing all tuples formed by extending the given tuples at the end with the given positions. A tuple is only extended with a position if that position did not already appear in the tuple.
-
Write a function permutations that takes the first word (str) and the second word (str) of an anagram. The function must return a set containing all permutations (tuple) describing the anagram.
-
Write a function isstar that takes the first word (str) and the second word (str) of an anagram. The function must return a Boolean value (bool) indicating whether the anagram is a star.
-
Write a function isperfect_star that takes the first word (str) and the second word (str) of an anagram. The function must return a Boolean value (bool) indicating whether the anagram is a perfect star.
These functions may assume that all arguments passed to them are valid, without the need to check this explicitly.
Example
>>> steps((4, 0, 1, 2, 3))
(1, 1, 1, 1, 1)
>>> steps((4, 1, 3, 0, 2))
(2, 2, 2, 2, 2)
>>> steps((2, 5, 1, 7, 4, 6, 3, 0))
(3, 4, 6, 5, 2, 5, 5, 2)
>>> steps((9, 2, 5, 8, 1, 4, 7, 0, 3, 6))
(3, 3, 3, 3, 3, 3, 3, 3, 3, 3)
>>> isstar_permutation((4, 0, 1, 2, 3))
False
>>> isstar_permutation((4, 1, 3, 0, 2))
True
>>> isstar_permutation((3, 1, 7, 5, 2, 4, 0, 6))
True
>>> isperfect_permutation((4, 0, 1, 2, 3))
True
>>> isperfect_permutation((4, 1, 3, 0, 2))
True
>>> isperfect_permutation((3, 1, 7, 5, 2, 4, 0, 6))
False
>>> positions('EARTH')
{'E': {0}, 'A': {1}, 'R': {2}, 'T': {3}, 'H': {4}}
>>> positions('CAREERS')
{'C': {0}, 'A': {1}, 'R': {2, 5}, 'E': {3, 4}, 'S': {6}}
>>> positions('DOWNLOAD')
{'D': {0, 7}, 'O': {1, 5}, 'W': {2}, 'N': {3}, 'L': {4}, 'A': {6}}
>>> positions('CESAROLITE')
{'C': {0}, 'E': {1, 9}, 'S': {2}, 'A': {3}, 'R': {4}, 'O': {5}, 'L': {6}, 'I': {7}, 'T': {8}}
>>> extend({()}, {2})
{(2,)}
>>> extend({(2,)}, {1, 5})
{(2, 1), (2, 5)}
>>> extend({(2, 1), (2, 5)}, {1, 5})
{(2, 1, 5), (2, 5, 1)}
>>> extend({(2, 1, 5), (2, 5, 1)}, {0, 7})
{(2, 1, 5, 0), (2, 1, 5, 7), (2, 5, 1, 0), (2, 5, 1, 7)}
>>> extend({(2, 1, 5, 0), (2, 1, 5, 7), (2, 5, 1, 0), (2, 5, 1, 7)}, {4})
{(2, 1, 5, 0, 4), (2, 1, 5, 7, 4), (2, 5, 1, 0, 4), (2, 5, 1, 7, 4)}
>>> extend({(2, 1, 5, 0, 4), (2, 1, 5, 7, 4), (2, 5, 1, 0, 4), (2, 5, 1, 7, 4)}, {6})
{(2, 1, 5, 0, 4, 6), (2, 1, 5, 7, 4, 6), (2, 5, 1, 0, 4, 6), (2, 5, 1, 7, 4, 6)}
>>> extend({(2, 1, 5, 0, 4, 6), (2, 1, 5, 7, 4, 6), (2, 5, 1, 0, 4, 6), (2, 5, 1, 7, 4, 6)}, {3})
{(2, 1, 5, 0, 4, 6, 3), (2, 1, 5, 7, 4, 6, 3), (2, 5, 1, 0, 4, 6, 3), (2, 5, 1, 7, 4, 6, 3)}
>>> extend({(2, 1, 5, 0, 4, 6, 3), (2, 1, 5, 7, 4, 6, 3), (2, 5, 1, 0, 4, 6, 3), (2, 5, 1, 7, 4, 6, 3)}, {0, 7})
{(2, 1, 5, 0, 4, 6, 3, 7), (2, 1, 5, 7, 4, 6, 3, 0), (2, 5, 1, 0, 4, 6, 3, 7), (2, 5, 1, 7, 4, 6, 3, 0)}
>>> permutations('EARTH', 'HEART')
{(4, 0, 1, 2, 3)}
>>> permutations('EARTH', 'HATER')
{(4, 1, 3, 0, 2)}
>>> permutations('CAREERS', 'CREASER')
{(0, 2, 3, 1, 6, 4, 5), (0, 2, 4, 1, 6, 3, 5), (0, 5, 3, 1, 6, 4, 2), (0, 5, 4, 1, 6, 3, 2)}
>>> permutations('DOWNLOAD', 'WOODLAND')
{(2, 1, 5, 0, 4, 6, 3, 7), (2, 1, 5, 7, 4, 6, 3, 0), (2, 5, 1, 0, 4, 6, 3, 7), (2, 5, 1, 7, 4, 6, 3, 0)}
>>> permutations('CESAROLITE', 'ESOTERICAL')
{(1, 2, 5, 8, 9, 4, 7, 0, 3, 6), (9, 2, 5, 8, 1, 4, 7, 0, 3, 6)}
>>> isstar('EARTH', 'HEART')
False
>>> isstar('EARTH', 'HATER')
True
>>> isstar('CAREERS', 'CREASER')
True
>>> isstar('DOWNLOAD', 'WOODLAND')
True
>>> isstar('CESAROLITE', 'ESOTERICAL')
True
>>> isperfect_star('EARTH', 'HEART')
False
>>> isperfect_star('EARTH', 'HATER')
True
>>> isperfect_star('CAREERS', 'CREASER')
True
>>> isperfect_star('DOWNLOAD', 'WOODLAND')
False
>>> isperfect_star('CESAROLITE', 'ESOTERICAL')
True
Epilogue
Cesàrolite is a hexagonal mineral PbMn4+3O6(OH)2 with hardness 4.5 and specific gravity 5.29. It occurs in spongy steel-gray masses and is supposed to be a hydrous lead manganate.
It was named in 1920 by Henri Jean Francois Buttgenbach and C. Gillet in honor of Giuseppe Raimondo Pio Cesàro (1849–1939), Professor of Mineralogy and Crystallography at the University of Liège (Belgium).
Epilogue
In 1998, as aerospace engineer Homer Hickam's memoir Rocket Boys was being adapted for the screen, Universal Studios' research warned that women over 30 would not see a movie with that title.
So the name was changed to October Sky — the same 10 letters in a different order.
Epilogue
The Mr. Mojo Risin' that appears repeatedly in the song L.A. Woman by The Doors is an anagram of their charismatic lead vocalist Jim Morrison.