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.

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 $(k,n)$-halsketting is een string (str) van $n$ letters die gekozen zijn uit de eerste $k$ ($1\le k\le 26$) letters van het alfabet. Zo is ABBEACEEA een voorbeeld van een $(5,9)$-halsketting. Merk op het niet nodig is dat alle mogelijke letters ook daadwerkelijk in de string voorkomen.

Twee halskettingen $h_1$ en $h_2$ zijn gelijk als $h_1$ kan omgevormd worden tot $h_2$ door enkele blokjes van het ene uiteinde naar het andere uiteinde te verschuiven.

Gevraagd wordt:

• Schrijf een functie rotatie waaraan een halsketting $h$ (str) en getal $r\in \mathbb{Z}$ (int) moeten doorgegeven worden. Als $r\ge 0$ dan moet de functie de halsketting teruggeven die we bekomen nadat we $r$ keer een blokje aan de linkerkant naar het andere uiteinde van de halsketting geschoven hebben. Als $r<0$ dan moet de functie de halsketting teruggeven die we bekomen nadat we $|r|$ keer een blokje aan de rechterkant naar het andere uiteinde van de halsketting geschoven hebben. Hierbij staat $|r|$ voor de absolute waarde van $r$.

• Schrijf een functie rotaties waaraan een halsketting $h$ (str) moet doorgegeven worden. De functie moet een verzameling (set) teruggeven met alle woorden (str) die met de halsketting $h$ 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 $h$.

• Schrijf een functie normaalvorm waaraan een halsketting $h$ (str) moet doorgegeven worden. De functie moet het alfabetisch eerst gerangschikte woord (str, in hoofdletters) teruggeven van alle woorden die met de halsketting $h$ kunnen gespeld worden door letters van het ene naar het andere uiteinde van de halsketting te schuiven. Dit woord wordt de normaalvorm van halsketting $h$ genoemd.

• Schrijf een functie halskettingen waaraan twee getallen $k\in {\mathbb{N}}_0$ (int) en $n\in \mathbb{N}$ (int) moeten doorgegeven worden. De functie moet teruggeven hoeveel (int) verschillende $(k,n)$-halskettingen er bestaan.

  Algoritme

  Dit zijn bijvoorbeeld de 24 verschillende $(3,4)$-halskettingen. In de oplijsting hebben we elke groep van gelijke halskettingen voorgesteld door de normaalvorm van die groep.

  AAAA   ABAC   ACCB
  AAAB   ABBB   ACCC
  AAAC   ABBC   BBBB
  AABB   ABCB   BBBC
  AABC   ABCC   BBCC
  AACB   ACAC   BCBC
  AACC   ACBB   BCCC
  ABAB   ACBC   CCCC

  De eenvoudigste manier om het aantal verschillende $(k,n)$- halskettingen te tellen is door alle $k^n$ mogelijke $(k,n)$-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 itertools¹ module uit The Python Standard Library².

Voorbeeld

                
            >>> rotatie('Jessica', 1)
'essicaJ'
>>> rotatie('emily', -2)
'lyemi'
>>> rotatie('LOUISE', 9)
'ISELOU'

>>> rotaties('Jessica')
{'CAJESSI', 'SICAJES', 'JESSICA', 'AJESSIC', 'SSICAJE', 'ESSICAJ', 'ICAJESS'}
>>> rotaties('emily')
{'YEMIL', 'ILYEM', 'EMILY', 'LYEMI', 'MILYE'}
>>> rotaties('LOUISE')
{'SELOUI', 'UISELO', 'ELOUIS', 'OUISEL', 'LOUISE', 'ISELOU'}

>>> normaalvorm('Jessica')
'AJESSIC'
>>> normaalvorm('emily')
'EMILY'
>>> normaalvorm('LOUISE')
'ELOUIS'

>>> halskettingen(2, 12)
352
>>> halskettingen(3, 7)
315
>>> halskettingen(9, 5)
11817
>>> halskettingen(21, 4)
48741
>>> halskettingen(26, 3)
5876