Существует ли алгоритм поиска наименьшего набора кратчайших префиксных подстрок непрерывной числовой последовательности?

Question

Прежде всего я хочу заранее поблагодарить всех, кто зайдет, за их терпение, у меня нет формального опыта работы в CS, поэтому я, вероятно, буду использовать некоторые из этих терминов неправильно.

У меня есть загадка:Учитывая два числа, которые определяют набор чисел непрерывного счета с одинаковым количеством цифр длиной примерно от 5 до 12 цифр (IE 50000 и 60000, 32325600000 и 32399999999), какой самый быстрый и эффективный способ сжать это число до набора префиксов, которые «содержат» все перестановки последующих цифр?

Используемый нами подход представляет собой гибрид обработки их как чисел и строк символов.Сначала удалите все пары совпадающих 0 и 9 в конце начала/конца.Во-вторых, создайте полную последовательность, скопированную в два столбца, где второй столбец всегда представляет собой подстроку с удаленной самой правой цифрой относительно первого столбца.Отсюда я могу рекурсивно подсчитать, сколько раз встречается данная подстрока, короткая на одну цифру, сохранить элементы, где N-count<10, а где N-count>=10, удалить еще одну цифру из обоих столбцов и повторить.

Мне интересно, есть ли более быстрый и эффективный способ сделать это.Операции со строками вместо математических вычислений были очевидным быстрым решением, но общий подход по-прежнему основан на рекурсивной группировке и обрезке символов.Я подумывал о создании полной серии столбцов префиксов и N-счетов, возвращающихся к старшей цифре, но, по крайней мере, инстинктивно мне кажется, что это будет менее эффективно, чем рекурсивная работа с уменьшающимся пулом чисел.

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

Предположим, что входной сигнал $а,б$, два $n$-цифровые длинные числа.Мы разрешаем ведущие нули (сейчас мы увидим, почему).Позволять $c$ быть самым длинным общим префиксом $а,б$, и разреши $а=cA$, $b=cB$.

Если $A = 0^{n-|c|}$ и $B = 9^{n-|c|}$ тогда мы просто выводим $c$ (это включает в себя случай $|c|=n$).

В противном случае, пусть $d_A$ быть первой цифрой $А$, и разреши $d_B$ быть первой цифрой $Б$.

Рекурсивно найти решение для диапазонов $[A,d_A 9^{|A|-1}]$ и $[d_B 0^{|B|-1},B]$, и префикс $c$ ко всему.Также добавьте $c(d_A+1),\ldots,c(d_B-1)$.

Вот неоптимизированная реализация Python:

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

Например, если вы запустите list(prefixes('50000000','55399999')) то вы получите следующий вывод:['50', '51', '52', '53', '54', '550', '551', '552', '553']