Consider a necklace with lettered beads that can slide along the string. Here's an example of a necklace whose beads spell the word JESSICA.

Necklace whose lettered beads spell the name JESSICA.

We could take leftmost bead J of the necklace and slide it around to the other end to spell the word ESSICAJ. We could also take the last two beads CA and slide them to the other end to spell the word CAJESSI.

Assignment

A $$(k, n)$$-necklace is a string (str) of $$n$$ chosen from the first $$k$$ ($$1 \leq k \leq 26$$) letters of the alphabet. For example, ABBEACEEA is a $$(5, 9)$$-necklace. Note that not every possible letter needs to appear in the string.

Two necklaces $$n_1$$ and $$n_2$$ are equal if $$h_1$$ can be transformed into $$h_2$$ by sliding some beads from one end to the other end.

Your task:

Write a function rotation that takes a necklace $$h$$ (str) and a number $$r \in \mathbb{Z}$$ (int). If $$r \geq 0$$ the function must return the necklace obtained after sliding the leftmost bead to the other end of the necklace $$r$$ times. If $$r < 0$$ the function must return the necklace obtained after sliding the rightmost bead to the other end of the necklace $$|r|$$ times, where $$|r|$$ represents the absolute of $$r$$.
Write a function rotations that takes a necklace $$h$$ (str). The functio must return the set containing all possible words (str) that can be spelled with necklace $$h$$ by sliding beads from one end to the other end of the necklace. All these words must be spelled in uppercase, irrespective of the use of uppercase and lowercase letters in necklace $$h$$.
Write a function normal_form that takes a necklace $$h$$ (str). The function must return the word (str, in uppercase) that comes first in lexicographic order among all words that can be spelled with necklace $$h$$ by sliding beads from one end to the other end of the necklace. This word is called the normal form of necklace $$h$$.
Write a function necklaces that takes two integers $$k \in \mathbb{N}_0$$ (int) and $$n \in \mathbb{N}$$ (int). The function must return the number (int) of distinct $$(k, n)$$-necklaces .
Algorithm

For example, here are the 24 distinct $$(3, 4)$$-necklaces. In listing the necklaces, we have represented each group of equal necklaces by their normal form.
```
AAAA   ABAC   ACCB
AAAB   ABBB   ACCC
AAAC   ABBC   BBBB
AABB   ABCB   BBBC
AABC   ABCC   BBCC
AACB   ACAC   BCBC
AACC   ACBB   BCCC
ABAB   ACBC   CCCC
```
The most straightforward way to count the number of distinct $$(k, n)$$-necklaces is to generate all $$k^n$$ possible $$(k, n)$$-necklaces, and deduplicate them using their normal form. This is an acceptable approach for this assignment. To generate all possible necklaces, you can use the functionality in the itertools¹ module from The Python Standard Library².

Example

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

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

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

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

Assignment

Algorithm

Example