
(* enumerate all necklaces with at most three colors *)

(* idea: first enumerate all strings, and then remove doublets *)

(**
 * Creates a list of all strings of length m with letters taken from
 * the given alphabet alph. 
 * The strings will be returned as lists of letters. It is assumed that
 * the elements of alph are distinct. 
 **)
ListOfStrings[alph_List, m_] := 
   Module[{i},

   Sort[Flatten[Outer[List, ##]& @@ Table[alph, {i, 1, m}], m-1]]
];

(**
 * Returns True iff a is a cyclic shift of b, e.g. {1,2,3} and {2,3,1} and 
 * {3,1,2} are the same in this sense, but {1,3,2} is something else. 
 **)
CyclicSameQ[a_List, b_List] :=
   Module[{l, i, j},

   If[ Length[a] =!= Length[b], Return[False] ];

   l = Length[a];

   Or @@ Table[ a[[ Table[1+Mod[j+i, l], {j, 1, l}] ]] === b, {i,1,l}]
];

(**
 * Returns the list of all strings of length m with letters taken from the
 * given alphabet alph, but only those which are not the same modulo
 * CyclicSameQ.
 **)
ListOfNecklaces[alph_, m_] :=
   Union[ListOfStrings[alph, m], SameTest -> CyclicSameQ];