Twee woorden vormen een anagram als het ene woord kan gevormd worden met de letters van het andere woord. Dit werkt in twee richtingen. We zullen een anagram echter bekijken als een paar woorden met een vaste volgorde en het tweede woord zien als een herschikking van de letters van het eerste woord, bijvoorbeeld CESAROLITE → ESOTERICAL.
Als de woorden uit $$n$$ letters bestaan, dan nummeren we de letters in het eerste woord van 0 tot en met $$n - 1$$. Een herschikking van de letters kunnen we dan beschrijven als een permutatie van hun posities. Het anagram CESAROLITE → ESOTERICAL met $$n = 10$$ letters, kunnen we bijvoorbeeld beschrijven als de permutatie (1, 2, 5, 8, 9, 4, 7, 0, 3, 6): de eerste letter van ESOTERICAL staat op positie 1 in CESAROLITE, de tweede letter op positie 2, de derde letter op positie 5, de vierde letter op positie 8, …, en de laatste letter op positie 6. We kunnen deze herschikking ook tekenen door de letters van het eerste woord rondom een cirkel te zetten en de opeenvolgende posities uit de permutatie met elkaar te verbinden, waarbij we ook de laatste positie met de eerste positie verbinden.
Deze permutatie verbindt de letters ES en TE die direct naast elkaar staan (oranje verbindingen). Een stervormig anagram is een speciaal soort anagram waarbij de letters maximaal door elkaar geschud worden: geen enkele letter staat in het tweede woord naast één van zijn originele buren in het eerste woord, waarbij we de eerste en de laatste letter ook als buren beschouwen.
Omdat de letter E twee keer voorkomt in het woord CESAROLITE, is er nog een tweede permutatie om het anagram CESAROLITE → ESOTERICAL te beschrijven: (9, 2, 5, 8, 1, 4, 7, 0, 3, 6). Als we deze permutatie tekenen, dan krijgen we een perfecte tienpuntige ster.
Jason Parker en Dan Barker zochten systematisch naar perfecte stervormige anagrammen onder alle Engelse woorden, en dit is het grootste dat ze vonden. Slechts 5.7 procent van alle anagrammen bleek stervormig te zijn, en zelfs die anagrammen leveren maar zelden een perfecte ster op.
Opgave
We gaan op zoek naar perfect stervormige anagrammen van woorden (str) die enkel uit hoofdletters bestaan.
We stellen een permutatie die een anagram met $$n$$ letters beschrijft voor als een tuple $$(p_0, p_1, \ldots, p_{n-1})$$, met $$p_i $$ (int; $$i = 0, 1, \ldots, n - 1$$) de getallen 0 tot en met $$n - 1$$ in willekeurige volgorde.
Om te bepalen of een permutatie $$(p_0, p_1, \ldots, p_{n-1})$$ een (perfecte) ster voorstelt, bepalen we een tuple $$(s_0, s_1, \ldots, s_{n-1})$$ met stappen $$s_i$$ (int; $$i = 0, 1, \ldots, n - 1$$). Als we voor de eenvoud stellen dat $$p_n \equiv p_0$$ (na de laatste positie in de permutatie komt terug de eerste positie), dan worden de stappen berekend als \[ s_i = (p_{i+1} - p_i)\!\!\!\!\mod{n} \] Daarbij staat $$s_i$$ voor het aantal stappen dat we in wijzerzin rondom de cirkel moeten zetten om van positie $$p_i$$ naar positie $$p_{i+1}$$ te gaan — twee opeenvolgende posities uit de permutatie die met elkaar verbonden worden. De bewerking $$a\!\!\!\mod{b}$$ staat voor de rest na gehele deling (het quotiënt) van $$a \in \mathbb{N}$$ door $$b \in \mathbb{N}_0$$ (modulo). Voor het anagram DOWNLOAD → WOODLAND met $$n = 8$$ letters krijgen we
| permutatie | 2 | 5 | 1 | 7 | 4 | 6 | 3 | 0 |
| stappen | 3 | 4 | 6 | 5 | 2 | 5 | 5 | 2 |
Een permutatie $$(p_0, p_1, \ldots, p_{n-1})$$ is stervormig als de getallen $$1$$ en $$n - 1$$ niet voorkomen in het tuple met stappen voor de permutatie. Als de permutatie $$1$$ stap zet, dan wordt een letter rondom de cirkel immers verbonden met zijn directe buur in wijzerzin. Als de permutatie $$n - 1$$ stappen zet, dan wordt een letter verbonden met zijn directe buur in tegenwijzerzin.
Een permutatie $$(p_0, p_1, \ldots, p_{n-1})$$ is perfect als alle getallen in het tuple met stappen voor de permutatie gelijk zijn. Als alle stappen gelijk zijn, dan zijn alle verbindingslijnen immers even lang.
Bovenstaande permutatie die het anagram DOWNLOAD → WOODLAND beschrijft, is dus wel stervormig maar niet perfect.
We gebruiken het anagram DOWNLOAD → WOODLAND ook om uit te leggen hoe je alle permutaties kunt vinden die een anagram beschrijven. Eerst nummeren we de posities van de letters van het eerste woord (DOWNLOAD) vanaf nul. Daarna starten we met een verzameling die enkel het lege tuple bevat. Voor elke letter van het tweede woord (WOODLAND) breiden we stelselmatig alle tuples in de verzameling uit met alle mogelijke posities waarop die letter voorkomt in het eerste woord. Een tuple wordt echter alleen uitgebreid met een positie, als die positie nog niet in het tuple voorkwam.
De eerste letter (W) van WOODLAND vinden we enkel op positie 2 in DOWNLOAD, dus breiden we het lege tuple uit tot het tuple (2), omdat positie 2 uiteraard nog niet in het lege tuple voorkwam. De tweede letter (O) van WOODLAND vinden we op posities 1 en 5 van DOWNLOAD, dus breiden we het tuple (2) uit tot de tuples (2, 1) en (2, 5) omdat zowel positie 1 als positie 5 nog niet in het tuple (2) voorkwamen. De derde letter (O) van WOODLAND vinden we op posities 1 en 5 van DOWNLOAD. We breiden het tuple (2, 1) dus uit tot het tuple (2, 1, 5), maar niet tot het tuple (2, 1, 1) omdat positie 1 al in het tuple (2, 1) voorkwam. Analoog breiden we het tuple (2, 5) uit tot het tuple (2, 5, 1), maar niet tot het tuple (2, 5, 5) omdat positie 5 al in het tuple (2, 5) voorkwam. Hierboven zie je hoe we de verzameling tuples verder uitbreiden met de overige letters van WOODLAND, om zo finaal een verzameling van vier permutaties te bekomen die het anagram DOWNLOAD → WOODLAND beschrijven.
We zeggen dat een anagram stervormig is als het beschreven wordt door minstens één stervormige permutatie. We zeggen dat een anagram perfect stervormig is als het beschreven wordt door minstens één stervormige permutatie die ook nog eens perfect is.
Gevraagd wordt:
-
Schrijf een functie stappen waaraan een permutatie (tuple) moet doorgegeven worden. De functie moet het tuple met de stappen (int) voor de permutatie teruggeven.
-
Schrijf een functie isstervormige_permutatie waaraan een permutatie (tuple) moet doorgegeven worden. De functie moet een Booleaanse waarde (bool) teruggeven, die aangeeft of de permutatie stervormig is.
-
Schrijf een functie isperfecte_permutatie waaraan een permutatie (tuple) moet doorgegeven worden. De functie moet een Booleaanse waarde (bool) teruggeven, die aangeeft of de permutatie perfect is.
-
Schrijf een functie posities waaraan een woord (str) moet doorgegeven worden. De functie moet een dictionary (dict) teruggeven, die elke letter (str) in het woord afbeeldt op een verzameling (set) met alle posities (int) waarop die letter in het woord voorkomt. Hierbij worden de posities van de letters van links naar rechts genummerd vanaf nul.
-
Schrijf een functie uitbreiden waaraan twee argumenten moeten doorgegeven worden: i) een verzameling (set) met tuples (tuple) van posities (int), en ii) een verzameling (set) met posities (int). De functie moet een nieuwe verzameling (set) teruggeven met alle tuples die gevormd worden door de gegeven tuples achteraan uit te breiden met de gegeven posities. Hierbij wordt een tuple enkel uitgebreid met een positie, als die positie nog niet in het tuple voorkwam.
-
Schrijf een functie permutaties waaraan het eerste woord (str) en het tweede woord (str) van een anagram moeten doorgegeven worden. De functie moet een verzameling (set) teruggeven met alle permutaties (tuple) die het anagram beschrijven.
-
Schrijf een functie isster waaraan het eerste woord (str) en het tweede woord (str) van een anagram moeten doorgegeven worden. De functie moet een Booleaanse waarde (bool) teruggeven, die aangeeft of het anagram stervormig is.
-
Schrijf een functie isperfecte_ster waaraan het eerste woord (str) en het tweede woord (str) van een anagram moeten doorgegeven worden. De functie moet een Booleaanse waarde (bool) teruggeven, die aangeeft of het anagram perfect stervormig is.
De functies mogen ervan uitgaan dat alle argumenten die eraan doorgegeven worden geldig zijn, zonder dat dit expliciet moet gecontroleerd worden.
Voorbeeld
>>> stappen((4, 0, 1, 2, 3))
(1, 1, 1, 1, 1)
>>> stappen((4, 1, 3, 0, 2))
(2, 2, 2, 2, 2)
>>> stappen((2, 5, 1, 7, 4, 6, 3, 0))
(3, 4, 6, 5, 2, 5, 5, 2)
>>> stappen((9, 2, 5, 8, 1, 4, 7, 0, 3, 6))
(3, 3, 3, 3, 3, 3, 3, 3, 3, 3)
>>> isstervormige_permutatie((4, 0, 1, 2, 3))
False
>>> isstervormige_permutatie((4, 1, 3, 0, 2))
True
>>> isstervormige_permutatie((3, 1, 7, 5, 2, 4, 0, 6))
True
>>> isperfecte_permutatie((4, 0, 1, 2, 3))
True
>>> isperfecte_permutatie((4, 1, 3, 0, 2))
True
>>> isperfecte_permutatie((3, 1, 7, 5, 2, 4, 0, 6))
False
>>> posities('EARTH')
{'E': {0}, 'A': {1}, 'R': {2}, 'T': {3}, 'H': {4}}
>>> posities('CAREERS')
{'C': {0}, 'A': {1}, 'R': {2, 5}, 'E': {3, 4}, 'S': {6}}
>>> posities('DOWNLOAD')
{'D': {0, 7}, 'O': {1, 5}, 'W': {2}, 'N': {3}, 'L': {4}, 'A': {6}}
>>> posities('CESAROLITE')
{'C': {0}, 'E': {1, 9}, 'S': {2}, 'A': {3}, 'R': {4}, 'O': {5}, 'L': {6}, 'I': {7}, 'T': {8}}
>>> uitbreiden({()}, {2})
{(2,)}
>>> uitbreiden({(2,)}, {1, 5})
{(2, 1), (2, 5)}
>>> uitbreiden({(2, 1), (2, 5)}, {1, 5})
{(2, 1, 5), (2, 5, 1)}
>>> uitbreiden({(2, 1, 5), (2, 5, 1)}, {0, 7})
{(2, 1, 5, 0), (2, 1, 5, 7), (2, 5, 1, 0), (2, 5, 1, 7)}
>>> uitbreiden({(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)}
>>> uitbreiden({(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)}
>>> uitbreiden({(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)}
>>> uitbreiden({(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)}
>>> permutaties('EARTH', 'HEART')
{(4, 0, 1, 2, 3)}
>>> permutaties('EARTH', 'HATER')
{(4, 1, 3, 0, 2)}
>>> permutaties('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)}
>>> permutaties('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)}
>>> permutaties('CESAROLITE', 'ESOTERICAL')
{(1, 2, 5, 8, 9, 4, 7, 0, 3, 6), (9, 2, 5, 8, 1, 4, 7, 0, 3, 6)}
>>> isster('EARTH', 'HEART')
False
>>> isster('EARTH', 'HATER')
True
>>> isster('CAREERS', 'CREASER')
True
>>> isster('DOWNLOAD', 'WOODLAND')
True
>>> isster('CESAROLITE', 'ESOTERICAL')
True
>>> isperfecte_ster('EARTH', 'HEART')
False
>>> isperfecte_ster('EARTH', 'HATER')
True
>>> isperfecte_ster('CAREERS', 'CREASER')
True
>>> isperfecte_ster('DOWNLOAD', 'WOODLAND')
False
>>> isperfecte_ster('CESAROLITE', 'ESOTERICAL')
True
Epiloog
Cesàrolite is een zeshoekig mineraal PbMn4+3O6(OH)2 met hardheid 4.5 en soortelijk gewicht 5.29. Het komt voor in sponsachtige staalgrijze massa's en is vermoedelijk een waterhoudend loodmanganaat.
Het werd in 1920 beschreven door Henri Jean Francois Buttgenbach en C. Gillet. Ze vernoemden het eervol naar Giuseppe Raimondo Pio Cesàro (1849–1939), een Italiaanse hoogleraar in de mineralogie en kristallografie aan de Universiteit van Luik (België).
Epiloog
Toen de biografie Rocket Boys van ruimtevaartingenieur Homer Hickam in 1998 werd verfilmd, wees onderzoek van Universal Studios uit dat vrouwen boven de 30 weinig interesse zouden tonen om naar een film met die titel te gaan kijken.
Dus werd de naam veranderd in October Sky — dezelfde 10 letters maar in een andere volgorde.
Epiloog
De Mr. Mojo Risin' die herhaaldelijk voorkomt in het nummer L.A. Woman van The Doors is een anagram van hun charismatische zanger Jim Morrison.