Gibt es einen Algorithmus, um die kleinste Menge der kürzesten Präfix-Teilzeichenfolgen einer fortlaufenden numerischen Folge zu finden?

Question

Zuallererst möchte ich allen, die vorbeischauen, für ihre Geduld danken. Ich habe keinen formellen CS-Hintergrund und werde daher wahrscheinlich einige dieser Begriffe falsch verwenden.

Ich habe ein Rätsel:Wenn wir zwei Zahlen angeben, die einen Satz kontinuierlich zählender Zahlen mit der gleichen Anzahl von Ziffern und einer Länge zwischen etwa 5 und 12 Ziffern definieren (z. B. 50000 und 60000, 32325600000 und 32399999999), wie lässt sich dies am schnellsten und effizientesten auf einen Satz zusammenfassen? von Präfixen, die alle Permutationen nachfolgender Ziffern „enthalten“?

Der von uns verwendete Ansatz ist eine Mischung aus der Behandlung dieser Werte als Zahlen und Zeichenfolgen.Entfernen Sie zunächst alle Paare übereinstimmender Nullen und Neunen am Ende des Anfangs/Endes.Erstellen Sie zweitens die vollständige Sequenz, die in zwei Spalten kopiert wird, wobei die zweite Spalte immer eine Teilzeichenfolge ist, bei der die Ziffer ganz rechts relativ zur ersten Spalte entfernt wird.Von dort aus kann ich rekursiv zählen, wie oft eine gegebene, um eine Ziffer kürzere Teilzeichenfolge vorkommt, die Elemente behalten, bei denen N-Anzahl <10 ist und bei denen N-Anzahl>=10 eine weitere Ziffer aus beiden Spalten entfernt und den Vorgang wiederholt.

Ich frage mich, ob es einen schnelleren und effizienteren Weg gibt, dies zu tun.String-Operationen anstelle von Mathematik waren offensichtlich eine schnelle Lösung, aber der allgemeine Ansatz basiert immer noch auf der rekursiven Gruppierung und dem Abschneiden von Zeichen.Ich habe darüber nachgedacht, eine vollständige Reihe von Präfix- und N-Zählungsspalten zu erstellen, die auf die höchste Ziffer zurückgehen, aber zumindest instinktiv fühlt sich das so an, als wäre das weniger effizient, als rekursiv mit einem abnehmenden Zahlenpool zu arbeiten.

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

Angenommen, die Eingabe ist $a,b$, zwei $n$-stellige lange Zahlen.Wir erlauben führende Nullen (wir werden gleich sehen, warum).Lassen $c$ sei das längste gemeinsame Präfix von $a,b$, und lass $a=cA$, $b=cB$.

Wenn $A = 0^{n-|c|}$ Und $B = 9^{n-|c|}$ dann geben wir einfach aus $c$ (Dazu gehört auch der Fall $|c|=n$).

Ansonsten lass $d_A$ sei die erste Ziffer von $A$, und lass $d_B$ sei die erste Ziffer von $B$.

Finden Sie rekursiv eine Lösung für die Bereiche $[A,d_A 9^{|A|-1}]$ Und $[d_B 0^{|B|-1},B]$, und Präfix $c$ zu allem.Fügen Sie außerdem hinzu $c(d_A+1),\ldots,c(d_B-1)$.

Hier ist eine nicht optimierte Python-Implementierung:

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

Zum Beispiel, wenn Sie laufen list(prefixes('50000000','55399999')) dann erhält man folgende Ausgabe:['50', '51', '52', '53', '54', '550', '551', '552', '553']