¿Hay un algoritmo para encontrar el conjunto más pequeño de las subcadenas de prefijo más cortas de una secuencia numérica continua?

Question

Antes de cualquier cosa que quiera agradecer preventivamente a alguien que caiga por su paciencia, no tengo ningún fondo formal CS, así que probablemente voy a usar algunos de estos términos incorrectos.

Tengo un rompecabezas: Dos números que definen un conjunto de números de conteo continuo del mismo número de dígitos, entre aproximadamente 5 y 12 dígitos (es decir, 50000 y 60000, 32325600000 y 32399999999999999999999), lo que es el más rápido y eficiente ¿Manera de condensar esto a un conjunto de prefijos que "contienen" todas las permutaciones de dígitos posteriores?

El enfoque que hemos estado usando es un híbrido para tratar estos números y cadenas de caracteres. Primero elimine cualquier par de 0 y 9 coincidentes al final del inicio / final. Segundo Crea la secuencia completa copiada a dos columnas, donde la segunda columna siempre es una subcadena con el dígito más a la derecha eliminada con respecto a la primera columna. Desde allí, puedo contar recursivamente la cantidad de veces que se produce una subcadena de un dígito que se le da, mantenga los elementos donde N-COUNT <10, y donde el número n-conteo>= 10 retire otro dígito de ambas columnas y repita.

Lo que me pregunto es si hay una manera más rápida y eficiente de hacer esto. Las operaciones de cadena en lugar de Matemáticas fueron una solución rápida obvia, pero el enfoque general aún se basa en agrupar y cortar recursivamente los personajes. He considerado hacer una serie completa de columnas de prefijo y N-Count que regresan al dígito más alto, pero al menos instintivamente, lo que se siente como si fuera menos eficiente que operar recursivamente en un grupo de números decrecientes.

IE
Input: 
Start=50000000 
End=55399999

which becomes
Start=500 
End=553

Cycle one creates two sequence columns like this:

String   Prefix     N-Count
500        50          10
501        50          10
etc..                  
510        51          10
etc..
550        55          6
551        55          6
552        55          6
553        55          6   

Cycle two keeps everything where N-count<10 the same, but reduces the rest by 1
digit each and recalculates N-count (while getting rid of duplicates).

String   Prefix     N-Count
50        5          5
51        5          5
52        5          5         
53        5          5
54        5          5       
550       55         4
551       55         4
552       55         4
553       55         4  


Output:  50,51,52,53,54,55,550,551,552,553 
```

Answer 1

Supongamos que la entrada es $ a, b $ , dos $ n $ -digit largos números. Permitimos los cereos principales (veremos en un momento por qué). Deje que $ C $ sea el prefijo común más largo de $ a, b $ y deje $ A= CA $ , $ b= cb $ .

Si $ a= 0 ^ {n- | c |} $ y $ b= 9 ^ {n- | c |} $ Luego, simplemente salimos $ c $ (esto incluye el caso $ | c |= n $ ).

De lo contrario, permita que $ d_a $ sea el primer dígito de $ a $ , y deje que $ D_B $ Sé el primer dígito de $ b $ .

Encuentre recursivamente una solución para los rangos $ [a, d_a 9 ^ {| a | -1}] $ y $ [d_b 0 ^ {| b | -1}, b] $ y prefijo $ C $ a todo. Además, agregue $ c (d_a + 1), \ ldots, c (d_b-1) $ .

Aquí hay una implementación de Python sin optimice:

def prefixes(a,b,C=''):
     n, m = len(a), max(i for i in range(len(a)+1) if a[:i] == b[:i])
     c, A, B = C+a[:m], a[m:], b[m:]
     if A == '0'*len(A) and B == '9'*len(B):
         yield c
     else:
         yield from prefixes(A[1:],'9'*(len(A)-1),c+A[0])
         for i in range(int(A[0])+1,int(B[0])):
             yield f'{c}{i}'
         yield from prefixes('0'*(len(B)-1),B[1:],c+B[0])

Por ejemplo, si ejecuta list(prefixes('50000000','55399999')), entonces obtiene la siguiente salida: ['50', '51', '52', '53', '54', '550', '551', '552', '553']