Encontrar la solución entera más cercana a una ecuación lineal

Question

Estoy interesado en calcular el número máximo de cadenas de una longitud fija que puede generar una expresión regular.

Si tengo la expresión regular ((a|b)c)+

¿Cómo puedo saber cuántas cadenas puedo construir a partir de un número que no exceda, por ejemplo, de 5?

En este caso concreto, no puedo construir una cadena que se ajuste a la regex que tenga exactamente 5 caracteres, pero puedo encontrar cadenas que tengan 4 caracteres, o 6.

Creo que la ecuación lineal sería algo así como

((a*x + b*y)+c)*z = I

with restrictions:
c=1
x>=0, y>= 0, z >=0
if(x = 0, y > 0)
if(y = 0, x >0

Si esta solución no es un número entero, ¿hay alguna manera de encontrar la solución entera más cercana, o sólo tengo que resolver la ecuación para diferentes valores de I?

Answer 1

Primero haz la observación de que cada nuevo par de letras permite duplicar el número de combinaciones.

Se puede escribir como una optimización lineal por mínimos cuadrados.

$$\min_v \|\bf Mv\|$$ Hago $\bf M$ innecesariamente grande para que el patrón sea más fácil de detectar: $${\bf M} = \left[\begin{array}{rrrrrrrrrrrrrrrrrrr} 0&2&0&-1&0&0&0&0&0&0&0&0&0\\ 0&0&0&2&0&-1&0&0&0&0&0&0&0\\ 0&0&0&0&0&2&0&-1&0&0&0&0&0\\ 0&0&0&0&0&0&0&2&0&-1&0&0&0\\ 0&0&0&0&0&0&0&0&0&2&0&-1&0 \end{array}\right]$$

Pero también necesitamos imponer una condición de contorno: por ejemplo que haya 2 soluciones de 2 letras. Podemos hacerlo añadiendo un término

$$+\epsilon {\bf C}\|{\bf v}-[0,2,0,\cdots]^T\|_2^2$$

Donde $\bf C$ es la matriz diagonal 0 en todas partes excepto en ${\bf C}_{22} = 1$ . Esto forzará la segunda posición de $\bf v$ para ser 2.

Ahora la respuesta real sería sumar el vector solución ya que queremos la suma de todas las combinaciones de longitudes 1,2,3,4,5. Pero eso se hace fácilmente cuando hemos resuelto el sistema.

---

EDIT: Variaciones Si, por ejemplo, tuviéramos $(a|b)+$ tendríamos:

$${\bf M} = \left[\begin{array}{rrrrrrrrrrrrrrrrrrr} 2&-1&0&0&0&0&0\\ 0&2&-1&0&0&0&0\\ 0&0&2&-1&0&0&0\\ 0&0&0&2&-1&0&0\\ 0&0&0&0&2&-1&0 \end{array}\right]$$

Porque entonces cada La nueva letra puede tomar cualquiera de los 2 nuevos valores. No es necesario saltar sobre cada segunda letra con un "0" en el sistema de ecuaciones que habría sido forzado a ser "c" en la expresión anterior.

Si tuviéramos $((a|b|c)d)+$ tendríamos:

$${\bf M} = \left[\begin{array}{rrrrrrrrrrrrrrrrrrr} 0&3&0&-1&0&0&0&0&0&0&0&0&0\\ 0&0&0&3&0&-1&0&0&0&0&0&0&0\\ 0&0&0&0&0&3&0&-1&0&0&0&0&0\\ 0&0&0&0&0&0&0&3&0&-1&0&0&0\\ 0&0&0&0&0&0&0&0&0&3&0&-1&0 \end{array}\right]$$

Porque habría 3 nuevos casos para multiplicar por cada nueva ocurrencia de $((a|b|c)d)$