Existe-t-il un algorithme permettant de trouver le plus petit ensemble de sous-chaînes de préfixes les plus courtes d'une séquence numérique continue ?

Question

Avant tout, je tiens à remercier de manière préventive tous ceux qui passent pour leur patience. Je n'ai aucune expérience formelle en CS, je vais donc probablement mal utiliser certains de ces termes.

J'ai une énigme :Étant donné deux nombres qui définissent un ensemble de nombres à comptage continu du même nombre de chiffres, entre environ 5 et 12 chiffres (IE 50000 et 60000, 32325600000 et 32399999999), quel est le moyen le plus rapide et le plus efficace de condenser cela en un ensemble de préfixes qui « contiennent » toutes les permutations de chiffres suivants ?

L'approche que nous avons utilisée est un hybride consistant à les traiter comme des nombres et des chaînes de caractères.Supprimez d’abord toutes les paires de 0 et de 9 correspondants à la fin du début/de la fin.Créez ensuite la séquence complète copiée sur deux colonnes, où la deuxième colonne est toujours une sous-chaîne dont le chiffre le plus à droite est supprimé par rapport à la première colonne.À partir de là, je peux compter de manière récursive combien de fois une sous-chaîne plus courte à un chiffre se produit, conserver les éléments où N-count<10 et où N-count>=10 supprimer un autre chiffre des deux colonnes et répéter.

Ce que je me demande, c'est s'il existe un moyen plus rapide et plus efficace de procéder.Les opérations sur les chaînes au lieu des mathématiques étaient une solution rapide évidente, mais l'approche générale repose toujours sur le regroupement et la suppression récursive de caractères.J'ai envisagé de créer une série complète de colonnes de préfixe et de nombre N remontant au chiffre le plus élevé, mais au moins instinctivement, cela semble moins efficace que d'opérer de manière récursive sur un pool de nombres décroissant.

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

Supposons que l'entrée soit $a,b$, deux $n$nombres longs à chiffres.Nous autorisons les zéros non significatifs (nous verrons dans un instant pourquoi).Laisser $c$ être le préfixe commun le plus long de $a,b$, et laisse $a=cA$, $b=cB$.

Si $A = 0^{n-|c|}$ et $B = 9^{n-|c|}$ alors nous sortons simplement $c$ (cela inclut le cas $|c|=n$).

Sinon, laissez $d_A$ être le premier chiffre de $A$, et laisse $d_B$ être le premier chiffre de $B$.

Trouver récursivement une solution pour les plages $[A,d_A 9^{|A|-1}]$ et $[d_B 0^{|B|-1},B]$, et préfixe $c$ à tout.Ajoutez également $c(d_A+1),\ldots,c(d_B-1)$.

Voici une implémentation Python non optimisée :

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])

Par exemple, si vous exécutez list(prefixes('50000000','55399999')) alors vous obtenez le résultat suivant :['50', '51', '52', '53', '54', '550', '551', '552', '553']