I need an algorithm to produce all strings with the following property. Here capital letter refer to strings, and small letter refer to characters. $XY$ means the concatenation of string $X$ and $Y$.
Let $\Sigma = \{a_0, a_1,\ldots,a_n,a_0^{-1},a_1^{-1},\ldots,a_n^{-1}\}$ be the set of usable characters. Every string is made up of these symbols.
Out put any set $S_n$ with the following property achieves the goal.($n\geq 2$)
If $W\in S_n$, then any cyclic shift of $W$ is not in $S_n$
If $W\in S_n$, then $|W| = n$
If $W\in S_n$, then $W \neq Xa_ia_i^{-1}Y$, $W \neq Xa_i^{-1}a_iY$, $W \neq a_iXa_i^{-1}$ and $W \neq a_i^{-1}Xa_i$ for any string $X$ and $Y$.
If $W\not \in S_n$, $S_n \cup \{W\}$ will violate at least one of the above 3 properties.
Clearly any algorithm one can come up with is an exponential algorithm. but I'm still searching for a fast algorithm because this have some practical uses. At least for $\Sigma=\{a_0,a_1,a_0^{-1},a_1^{-1}\}$ and $n<25$.
The naive approach for my practical application requires $O(4^n)$ time. It generate all strings of length n. When ever a new string is generated, the program create all cyclic permutations of the string and check if it have been generated before though a hash table. If not, add to the list of the result strings. Total amount of operation are $O(n4^n)$, and that's assuming perfect hashing. 12 is the limit.
Are there better approaches? clearly a lot of useless strings were generate.
Edit: The practical usage is to find the maximum of minimum self intersection of a curve on a torus with a hole. Every curve can be characterized by a string described above. Therefore I have to generate every string and feed it to a program that calculate the minimum self intersection.