Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$)

  1. If $W\in S_n$, then any cyclic shift of $W$ is not in $S_n$

  2. If $W\in S_n$, then $|W| = n$

  3. 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$.

  4. 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.

share|improve this question
2  
It sounds like you're trying to generate something like Lyndon words, but in a free group rather than a free monoid. If you search the literature with that keyword you might find something useful. –  Qiaochu Yuan Aug 12 '10 at 22:50
    
In statement 1 I assume that you mean that for any string no cyclic shift of it is in S, in other words that $X$ and one of $Y$ and $Z$ are nonempty. Does statement 3 hold for cyclic shifts as well? i.e. are strings of the form $a_i^{-1}Xa_i$ and its reverse permitted? –  deinst Aug 13 '10 at 0:29
    
@deinst, thx for pointing it out. I just added it. –  Chao Xu Aug 13 '10 at 1:15
1  
Perhaps briefly describing the "practical application" would motivate more people to work on this question? –  rgrig Aug 13 '10 at 14:00
    
It seems, that size of S_n for n=24 is about 1.9*10^11. Therefore you will need a few terabytes for this sequence. –  Fiktor Aug 14 '10 at 0:57

2 Answers 2

up vote 4 down vote accepted

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.

share|improve this answer
    
There is a bug somewhere. for n=5, it generates [-2, -1, 2, -2, 1]. I'm going to try find what the problem was. –  Chao Xu Aug 14 '10 at 21:28
    
Doh! Operator precedence bites me. I should know better. The decision to output should be if (i == n) and ((l[w[1]] + l[w[n]]) != 0): –  deinst Aug 15 '10 at 1:40
    
That still doesn't fix the problem. output [-2, -1, 2, -2, 1] satisfies l[w[1]]+l[w[n]]!=0. Of course a quick fix it is to loop though all l[w[i]]+l[w[i+1]]!=0. Since the code already removed most of the wrong strings anyway. This code is good enough for me for all the prime numbers below 20. Thanks. I'm currently looking at citeseerx.ist.psu.edu/viewdoc/… –  Chao Xu Aug 15 '10 at 4:03
    
That is strange. I get i=3 when w = [-2 -1 2 -2 1]. Are you getting i == 5? –  deinst Aug 15 '10 at 13:18
    
I get i==5. I used the exact code after your edit. –  Chao Xu Aug 19 '10 at 20:02

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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