8
$\begingroup$

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.

  • 0
    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. – 2010-08-14

2 Answers 2

4

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.

  • 0
    I get i==5. I used the exact code after your edit. – 2010-08-19
1

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.