Generate the k-ary necklaces of length n

Question

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}, {&, 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]

Answer 1

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

Answer 2

Python 2, 105 bytes

lambda k,n:{min(i[j:]+i[:j]for j in range(n or 1))for i in product(*[range(k)]*n)}
from itertools import*

Try it online!

Returns a set of tuples.

Answer 3

JavaScript (ES7),  123 116 115  113 bytes

Takes input as (k)(n). Each necklace is represented as an array of integers.

k=>g=(n,x=k**n,o=[])=>x--?g(n,x,o.some(a=>~(a+[,a]).search(b),b=[...Array(n)].map(_=>x/k**--n%k|0))?o:[b,...o]):o

Try it online!

Answer 4

Japt, 27 bytes

?UÆVoÃrï ®c £ZéYÃn gÃâ:[[]]

Try it online!

Outputs with numbers starting from 0 for the values. Inputs in reversed order (n then k). The r throws a fit for n = 0 so I had to add an significant special-case.

Explanation:

?                     :[[]]    #Special case: return [[]] if n is 0
 UÆ  Ã                         #Get n rows of:
   Vo                          # The numbers [0..k-1]
      rï                       #Get all possible lists containing one number from each row...
         ®          Ã          #For each of those lists:
          c                    # Fix the formatting
            £ZéYÃ              # Get every possible rotation
                 n g           # Choose the "minimum" one
                     â         #Remove duplicate lists

Answer 5

Charcoal, 37 bytes

Ｎθ≔Ｘθ…⁰⊕Ｎη≔⊟ηζ¿ηＩＥΦζ⁼κ⌊﹪÷×ι⊕ζηζ﹪÷ιηθ¶

Try it online! Link is to verbose version of code. Explanation:

Ｎθ≔Ｘθ…⁰⊕Ｎη≔⊟ηζ

Input k and n and calculate the powers of k from 1 to n, but then keep kⁿ separately.

¿η...¶

If n is zero then just print a newline. (I could special-case 0 in the algorithm which would only cost two bytes but the resulting array only contains an empty array and Charcoal optimises that away on output, so you can't tell that the empty array is there.)

Φζ⁼κ⌊﹪÷×ι⊕ζηζ

For all the numbers from 0 to kⁿ, multiply them all by kⁿ+1, then divide by the above powers of k, then take the modulus of all of them by kⁿ. Keep only those numbers which equal the minimum of the resulting set.

ＩＥ...﹪÷ιηθ

Convert the numbers to reversed base k padded to length n for output using Charcoal's default output which is each element on its own line and each necklace double-spaced from the next necklace.