¿Una forma rápida de generar cadenas cíclicas con pocas restricciones?

Question

Necesito un algoritmo que produzca todas las cadenas con la siguiente propiedad. Aquí la letra mayúscula se refiere a las cadenas, y la letra minúscula a los caracteres. $XY$ significa la concatenación de la cadena $X$ y $Y$ .

Dejemos que $\Sigma = \{a_0, a_1,\ldots,a_n,a_0^{-1},a_1^{-1},\ldots,a_n^{-1}\}$ sea el conjunto de caracteres utilizables. Toda cadena está formada por estos símbolos.

Poner fuera cualquier conjunto $S_n$ con la siguiente propiedad logra el objetivo.( $n\geq 2$ )

1. Si $W\in S_n$ entonces cualquier desplazamiento cíclico de $W$ no está en $S_n$

2. Si $W\in S_n$ entonces $|W| = n$

3. Si $W\in S_n$ entonces $W \neq Xa_ia_i^{-1}Y$ , $W \neq Xa_i^{-1}a_iY$ , $W \neq a_iXa_i^{-1}$ y $W \neq a_i^{-1}Xa_i$ para cualquier cadena $X$ y $Y$ .

4. Si $W\not \in S_n$ , $S_n \cup \{W\}$ violará al menos una de las 3 propiedades anteriores.

Está claro que cualquier algoritmo que se pueda inventar es un algoritmo exponencial. pero sigo buscando un algoritmo rápido porque esto tiene algunos usos prácticos. Al menos para $\Sigma=\{a_0,a_1,a_0^{-1},a_1^{-1}\}$ y $n<25$ .

El enfoque ingenuo para mi aplicación práctica requiere $O(4^n)$ tiempo. Genera todas las cadenas de longitud n. Cuando se genera una nueva cadena, el programa crea todas las permutaciones cíclicas de la cadena y comprueba si se han generado antes a través de una tabla hash. Si no es así, la añade a la lista de cadenas resultantes. La cantidad total de operaciones son $O(n4^n)$ y eso suponiendo un hashing perfecto. 12 es el límite.

¿Hay mejores enfoques? Claramente se generaron muchas cadenas inútiles.

Edición: El uso práctico es encontrar el máximo de la auto intersección mínima de una curva en un toro con un agujero. Cada curva puede ser caracterizada por una cadena descrita anteriormente. Por lo tanto, tengo que generar cada cadena y alimentar a un programa que calcular la auto-intersección mínima.

Answer 1

Haciendo explícito lo que está implícito en el comentario de Qiaochu Yuan, y demostrando que el trabajo de otra persona no ha logrado evadir mis ojos. (Es un artículo estupendo, léalo). Presento esta adaptación del algoritmo de Duval.

Asigne un orden a sus símbolos, por ejemplo $a_1, a_2, a_1^{-1}, a_2^{-1}$ que primer_símbolo y _último_símbolo sean el primer y el último símbolo del conjunto. Sea next una función que da el siguiente símbolo en la secuencia. La función conflicto comprueba si los dos símbolos son inversos entre sí.

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

Esto no es más que el algoritmo de Duval para generar una lista de los desplazamientos cíclicos lexicográficamente mínimos con comprobaciones adicionales para pasar por encima de los casos en los que debería producirse un conflicto. No me he molestado en elaborar una prueba formal de que esto funciona, ni lo he implementado en código real. Caveat Emptor.

Editar Como era de esperar, se me escapó un caso de esquina. El siguiente código python parece funcionar. Toma la longitud del ciclo y una lista de enteros (uso enteros para el grupo)

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

para obtener la longitud de cuatro ciclos para {-2, -1, 1, 2} llame a

cycles(4, [-2, -1, 1, 2])

lo que resulta en

[-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 ¿No dije que

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

Eso es lo que debería haber dicho si hubiera seguido mi propio consejo. Lo siento.

Answer 2

Primero de todos, usted puede estar interesado en el trabajo de Chas y Phillips: "la Auto-intersección de las curvas en la pinchada de toro". Sólo he desnatada en su papel, pero ellos parecen estar haciendo algo estrechamente relacionado con lo que usted desea.

Segundo quiero adivinar, por alguna razón, que el tiempo promedio para calcular la auto-intersección número es mucho más lento que el promedio de tiempo para generar una palabra. (Es que el caso? Me podría decir cómo se computing mínima auto-intersección de los números?)

Si es así, supongo que desea generar algunas cadenas como sea posible. Voy a usar las $a, A, b, B$ como el grupo electrógeno $\pi_1 = \pi_1(T)$. Mirando Lyndon palabras es esencialmente el mismo que se aplica interior de automorfismos (conjugación, es decir, la rotación cíclica) a sus palabras. También puede intentar sustituir una palabra $w$ por su inverso $W$. Si algunos de rotación de $W$ beats $w$ [sic], entonces usted puede lanzar $w$ distancia.

También hay otros "geométrica automorfismos" (elementos de la asignación de grupo de clase) de $\pi_1$ cuales son muy útiles por ejemplo la rotación de $T$ un cuarto:

$$a \mapsto b \mapsto A \mapsto B \mapsto a.$$

También hay dos bonitas reflexiones: corregir $b, B$ y swap $a$ $A$ o de la otra manera alrededor. Escribiendo estas líneas da la hyperelliptic que se intercambia $a$ $A$ y swaps $b$$B$. (Yo uso el de python swapcase función de esto, muy simple!)

Si ninguna de estas operaciones (o cualquier composiciones de estos, por ejemplo, la inversa de una palabra), que produce una palabra $w'$ que es lexicográficamente antes de $w$, entonces usted puede lanzar $w$ distancia.

Por favor, hágamelo saber si esto es útil, estoy interesado en este tipo de problema.