A fast way to generate cyclic strings with few restrictions? 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.
 A: Making explicit what is implicit in Qiaochu Yuan's comment, and demonstrating that someone else's work has failed to evade my eyes. (It is a neat article, read it.)  I present this adaptation of Duval's algorithm.
Assign an order to your symbols, say $a_1, a_2, a_1^{-1}, a_2^{-1}$ let first_symbol and _last_symbol be the first and last symbols in the set.  Let next be a function that gives the next symbol in sequence. The function conflict checks to see if the two symbols are inverses of each other.
w[1] <- first_symbol
i <- 1
repeat
  for j = 1 to n–i
    do w[i+j] <- w[j]
  if i = n and not conflict(w[1], w[n])
    then output w[1] ... w[n]
  i <- n
  while i > 0 and w[i] = last_symbol
    do i <- i–1
  if i > o  
     then w[i] <- next(w[i])
  if i > 1 and conflict(w[i-1], w[i]) 
     then w[i] <- next(w[i])
until i = 0

This is just Duval's algorithm for generating a list of the lexicographically minimal cyclic shifts with extra checks to step over the cases where a conflict should occur. I have neither bothered to work out either a formal proof that this works, or implemented it in actual code.  Caveat Emptor.
Edit As expected, I missed a corner case.  The following python code appears to work. It takes the length of the cycle and a list of integers (I use integers for the group)
def cycles(n,l):
    w = range(n+1)
    m = len(l) - 1
    w[1] = 0
    i = 1
    while i > 0:
        for j in range(n-i):
            w[j + i + 1] = w[j + 1]
        if i == n and l[w[1]] + l[w[n]] != 0:
            print [l[w[i]] for i in xrange(1,n+1)]
        i = n
        while i > 0 and w[i] == m:
            i = i - 1
        while i > 0:
            if i > 0:
                w[i] = w[i] + 1
            if i > 1 and l[w[i-1]] + l[w[i]] == 0:
                w[i] = w[i] + 1
            if w[i] <= m:
                break
            i = i - 1

to get the length four cycles for {-2, -1, 1, 2} call
cycles(4, [-2, -1, 1, 2])

resulting in
[-2, -2, -2, -1]
[-2, -2, -2, 1]
[-2, -2, -1, -1]
[-2, -2, 1, 1]
[-2, -1, -2, 1]
[-2, -1, -1, -1]
[-2, -1, 2, -1]
[-2, -1, 2, 1]
[-2, 1, 1, 1]
[-2, 1, 2, -1]
[-2, 1, 2, 1]
[-1, -1, -1, 2]
[-1, -1, 2, 2]
[-1, 2, 1, 2]
[-1, 2, 2, 2]
[1, 1, 1, 2]
[1, 1, 2, 2]
[1, 2, 2, 2]

Ahem Didn't I say
def cycles(n,l):
    w = range(n+1)
    m = len(l) - 1
    w[1] = 0
    i = 1
    while i > 0:
        for j in range(n-i):
            w[j + i + 1] = w[j + 1]
        if (i == n) and ((l[w[1]] + l[w[n]]) != 0):
            print [l[w[i]] for i in xrange(1,n+1)]
        i = n
        while i > 0 and w[i] == m:
            i = i - 1
        while i > 0:
            if i > 0:
                w[i] = w[i] + 1
            if (i > 1) and ((l[w[i-1]] + l[w[i]]) == 0):
                w[i] = w[i] + 1
            if w[i] <= m:
                break
            i = i - 1

That's what I should have said if I took my own advice.  Sorry.
A: First of all, you might be interested in the work of Chas and Phillips: "Self-intersection of curves on the punctured torus".  I've only skimmed their paper, but they seem to be doing something closely related to what you want.
Second I want to guess, for some reason, that the average time to compute self-intersection number is a lot slower than the average time to generate a word.  (Is that the case?  Could you tell me how you are computing minimal self-intersection numbers?)
If so, I guess that you want to generate as few strings as possible.  I'll use $a, A, b, B$ as the generating set for $\pi_1 = \pi_1(T)$.  Looking at Lyndon words is essentially the same as applying inner automorphisms (conjugation, ie cyclic rotation) to your words.   You might also try replacing a word $w$ by its inverse $W$.  If some rotation of $W$ beats $w$ [sic], then you can throw $w$ away. 
There are also other "geometric automorphisms" (elements of the mapping class group) 
of $\pi_1$ which are very useful eg rotation of $T$ by one-quarter: 
$$a \mapsto b \mapsto A \mapsto B \mapsto a.$$
There are also two nice reflections: either fix $b, B$ and swap $a$ with $A$, or the other way around.  Composing these gives the hyperelliptic which swaps $a$ with $A$ and swaps $b$ with $B$.  (I use python's swapcase function for this -- very simple!) 
If any of these operations (or any compositions of these, eg the reverse of a word) produces a word $w'$ that is lexicographically before $w$, then you can throw $w$ away.  
Please let me know if this is helpful -- I'm interested in this kind of problem. 
