6
\$\begingroup\$

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 , 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]
\$\endgroup\$
  • \$\begingroup\$ You could have a program that verifies outputs. I think examples would also be helpful. \$\endgroup\$ – lirtosiast Feb 1 at 19:27
  • \$\begingroup\$ @lirtosiast Well, that would also depend on the output format. Different languages have different notations for lists. I suppose I could make one for python and let people adapt it to different languages. Think that would help? \$\endgroup\$ – PyRulez Feb 1 at 19:39
  • \$\begingroup\$ Related \$\endgroup\$ – PyRulez Feb 1 at 19:44
  • 1
    \$\begingroup\$ Very closely related \$\endgroup\$ – Peter Taylor Feb 1 at 22:54
  • \$\begingroup\$ @PeterTaylor Indeed. One "gotcha" to look out for though is that the number of necklaces is not the same as the number of lyndon words, because a lyndon word also needs to be distinct from all its rotations. \$\endgroup\$ – PyRulez Feb 1 at 23:56
3
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ This appears to give the wrong answers if k or n are less than 2 (although I am not familiar enough with Jelly to know for sure). \$\endgroup\$ – PyRulez Feb 1 at 20:11
  • \$\begingroup\$ Fixed it to agree with given examples for a cost of 1 byte, are there any remaining issues? \$\endgroup\$ – Jonathan Allan Feb 1 at 20:48
  • 1
    \$\begingroup\$ I do not see any. The problems seemed related to empty and singleton lists, but those issues are now fixed. \$\endgroup\$ – PyRulez Feb 1 at 21:00
1
\$\begingroup\$

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!

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ On input (3,4), it seems to be missing a necklace corresponding to [3,2,1]. \$\endgroup\$ – PyRulez Feb 1 at 23:51
  • \$\begingroup\$ @PyRulez Fixed, I think \$\endgroup\$ – Kamil Drakari Feb 2 at 0:59
0
\$\begingroup\$

Charcoal, 37 bytes

Nθ≔Xθ…⁰⊕Nη≔⊟ηζ¿ηIEΦζ⁼κ⌊﹪÷×ι⊕ζηζ﹪÷ιηθ¶

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

Nθ≔Xθ…⁰⊕Nη≔⊟ηζ

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.

IE...﹪÷ιηθ

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.

\$\endgroup\$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.