Een halsketting bestaat uit een snoer waaraan blokjes hangen. Op elk
blokje staat één letter van het alfabet. Hieronder zie je
bijvoorbeeld een halsketting waarvan de blokjes het woord JESSICA
spellen.
Halsketting met blokjes die de naam JESSICA spellen.
De blokjes kunnen langs het snoer van de halsketting geschoven worden.
Als we in de halsketting uit het voorbeeld het blokje met de letter J
naar het andere uiteinde schuiven, dan spellen we op die manier het woord
ESSICAJ. We kunnen ook de laatste twee blokjes CA
nemen en naar het andere uiteinde schuiven, om zo het woord CAJESSI
te spellen.
Opgave
Een -halsketting is een string (str)
van letters die gekozen zijn uit de eerste () letters van het alfabet. Zo is ABBEACEEA een voorbeeld
van een -halsketting. Merk op het niet nodig is dat alle
mogelijke letters ook daadwerkelijk in de string voorkomen.
Twee halskettingen en zijn gelijk als
kan omgevormd worden tot door enkele blokjes van het ene
uiteinde naar het andere uiteinde te verschuiven.
Gevraagd wordt:
Schrijf een functie rotatie waaraan een halsketting
(str) en getal (int)
moeten doorgegeven worden. Als dan moet de functie de
halsketting teruggeven die we bekomen nadat we keer een blokje
aan de linkerkant naar het andere uiteinde van de halsketting
geschoven hebben. Als dan moet de functie de halsketting
teruggeven die we bekomen nadat we keer een blokje aan de
rechterkant naar het andere uiteinde van de halsketting geschoven
hebben. Hierbij staat voor de absolute waarde van .
Schrijf een functie rotaties waaraan een halsketting
(str) moet doorgegeven worden. De functie moet een
verzameling (set) teruggeven met alle woorden (str)
die met de halsketting kunnen gespeld worden door letters van
het ene naar het andere uiteinde van de halsketting te schuiven. Al
deze woorden moeten in hoofdletters gespeld worden, ongeacht het
gebruik van hoofdletters en kleine letters in halsketting .
Schrijf een functie normaalvorm waaraan een halsketting
(str) moet doorgegeven worden. De functie moet het
alfabetisch eerst gerangschikte woord (str, in
hoofdletters) teruggeven van alle woorden die met de halsketting
kunnen gespeld worden door letters van het ene naar het andere
uiteinde van de halsketting te schuiven. Dit woord wordt de normaalvorm
van halsketting genoemd.
Schrijf een functie halskettingen waaraan twee getallen
(int) en (int)
moeten doorgegeven worden. De functie moet teruggeven hoeveel (int)
verschillende-halskettingen er bestaan.
Algoritme
Dit zijn bijvoorbeeld de 24 verschillende -halskettingen.
In de oplijsting hebben we elke groep van gelijke halskettingen
voorgesteld door de normaalvorm van die groep.
De eenvoudigste manier om het aantal verschillende -
halskettingen te tellen is door alle mogelijke -halskettingen te genereren, en die daarna te ontdubbelen op
basis van hun normaalvorm. Dit is een aanvaardbare strategie voor
deze opgave. Om alle halskettingen te genereren, kan je gebruikmaken
van de functionaliteit in de itertools1 module uit The Python Standard Library2.