Generate the k-ary necklaces of length n The set of necklaces is the set of strings, where two strings are considered to be the same necklace if you can rotate one into the other. Your program will take nonnegative integers k and n, and generate a list of the k-ary (fixed) necklaces of length n.

Necklaces will be represented by any representative string. So the necklace corresponding to the strings {ABC, BCA, CAB} can represented as ABC, BCA, or CAB.

The program will output a list of strings, such that each necklace is represented by exactly one string in the list. So for instance, outputting ABC and BCA would not be valid, since the same necklace was represented twice.

Some other details:


Your program may choose which k characters to use for the alphabet. If you prefer, you can instead choose k distinct values of any type, and have your program output lists (or some other sequence type) of those k values. (This might in fact be necessary if k is greater than the number of characters avaible in your language.) For example, if k=3, you could use {A,B,C}, {&amp;, H, (}, or even {10, 11, 12} as your alphabet. The only restriction is that elements of your alphabet may not contain whitespace.
You may output any representative for each necklace. So for the necklace {ABC, BCA, CAB}, you may output ABC, BCA, or CAB. There is no "preferred" representative.


This is code-golf, so the shortest program wins!



Also, here is a useful test to see if your program is working. Given k and n, the list your program outputs have the length listed here. Here is an OEIS sequence corresponding to k=2.

Also, here are some examples and counterexamples. Note that these are not test cases, because any input has both an infinite number of correct and incorrect outputs. I will give inputs in the form (k,n).

Examples:


(2,2): [AA, BB, AB]
(2,2): [AA, BA, BB]
(2,2): [[1,0], [0,0], [1,1]]
(3,2): [AA, BB, CC, AB, BC, AC]
(2,3): [AAA, BBB, AAB, ABB]
(3,3): [AAA, BBB, CCC, AAB, AAC, ABB, ABC, ACB, ACC, BBC, BCC]
(0,n): [] (for positive integers n)
(k,0): [[]] (for nonnegative integers k)
(k,n): Search "necklaces with k colors and n beads" on wolfram alpha (for positive integers k and n)


Counterexamples:


(2,2): [AA, BB, AB, BA]
(2,2): [AA, BB]
(3,3): [AAA, BBB, CCC, AAB, AAC, ABB, ABC, ACC, BBC, BCC]
(3,3): [AAA, BBB, CCC, AAB, BAA, AAC, ABB, ABC, ACB, ACC, BBC, BCC]
(k,n): Any list whose length is different from this (for positive integers n)
(3,3): [AAA, BBB, CCC, AAB, BAA, AAC, ABB, ABC, ACC, BBC, BCC]
Jelly, 8 bytes

ṗṙJṂȯƲ€Q


A dyadic Link accepting the alphabet size, k, on the left and the necklace length, n, on the right which yields a list of the necklaces using the positive integers up to k as the alphabet.

Try it online!

How?

ṗṙJṂȯƲ€Q - Link: integer k, integer n
ṗ        - Cartesian power of [1,2,...,k] with n
         -   i.e. all n-length lists using alphabet [1,2,...,k]
     Ʋ€  - last four links as a monad for €ach list, L:
  J      -   range of length - i.e. [1,2,...,n]
 ṙ       -   rotate left by each of those values - i.e. get all rotations
   Ṃ     -   minimum
    ȯ    -   logical OR with L (since the minimum of an empty list is 0 not [])
      Q  - unique values the resulting list