Existe um algoritmo para encontrar o menor conjunto de menor prefixo substrings de uma contínua seqüência numérica?

Question

Antes de qualquer coisa, quero antecipadamente agradecer quem cai pela sua paciência, eu não tenho nenhum formal CS plano de fundo, então eu provavelmente vou usar alguns desses termos errado.

Eu tenho um quebra-cabeça:Dado dois números que definem um conjunto de contínuo, contagem de números com o mesmo número de dígitos, entre cerca de 5 e 12 dígitos (ou seja, 60000 50000 e, 32325600000 e 32399999999), que é a maneira mais rápida e eficiente para condensar esta para um conjunto de prefixos que "contêm" todas as permutações de dígitos subsequentes?

A abordagem que estamos usando é um híbrido de tratar esses números e cadeias de caracteres.Primeiro remova quaisquer pares de correspondência de 0's e 9's no final do início/fim.Segunda criar a sequência completa copiados para duas colunas, onde a segunda coluna é sempre uma subseqüência de caracteres com o dígito mais à direita removido em relação à primeira coluna.A partir daí eu posso recursivamente contar quantas vezes um dado de um dígito-menor substring ocorre, manter os itens que N-contagem<10, e onde N-count>=10 para remover outro dígito de ambas as colunas e repita.

O que eu estou querendo saber é se existe um percurso mais rápido e mais eficiente maneira de fazer isso.Operações de cadeia de caracteres em vez de matemática foi uma óbvia solução rápida, mas a abordagem geral ainda depende recursivamente agrupamento e cortando parte caracteres.Eu pensei em fazer uma série de Prefixo e N-contagem de colunas indo de volta para o maior dígito, mas pelo menos intuitivamente, que se sente como ele seria menos eficiente do que operacional recursivamente sobre a diminuição de um conjunto de números.

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

Suponha que a entrada é $a,$b, dois $n$dígitos de um número longo.Nós permitimos que os zeros à esquerda (vamos ver porquê).Deixe $c$ ser o maior prefixo comum de $a,$b, e deixe $a=cA$, $b=cB$.

Se $A = 0^{n|c|}$ e $B = 9^{n|c|}$ então nós simplesmente saída $c$ (isto inclui o caso $|c|=n$).

Caso, contrário, deixe $d_A$ seja o primeiro dígito do $A$, e deixe $d_B$ seja o primeiro dígito do $B$.

Recursivamente encontrar uma solução para os intervalos $[A,d_A 9^{|A|-1}]$ e $[d_B 0^{|B|-1},B]$, e o prefixo $c$ para tudo.Além disso, adicione $c(d_A+1),\ldots,c(d_B-1)$.

Aqui está um unoptimized python implementação:

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 exemplo, se você executar list(prefixes('50000000','55399999')) em seguida, você receber a seguinte saída:['50', '51', '52', '53', '54', '550', '551', '552', '553']