連続した数値シーケンスの最短プレフィックス部分文字列の最小セットを見つけるアルゴリズムはありますか？

Question

彼らの忍耐力のために落としてくれた人は誰にもいただきありがとうございました、私はおそらくこれらの用語のいくつかを間違って使うつもりです。

私はパズルを持っています：長い5桁の長さと12桁の同じ数の連続カウント数を定義する2つの数字を与えられます（つまり、50000と60000,32325600000、32399999999）、最速かつ最も効率的なものは何ですか？これを「含める」プレイクスのセットに続く桁数のすべての順列を集める方法は？

使用してきたアプローチは、これらを数字や文字の文字列として扱うハイブリッドです。まず、スタート/エンドの最後に一致した0と9のペアを削除します。 2番目の列にコピーされたフルシーケンスを作成します。ここで、2列目は常に最初の列に対して右端の桁が削除された部分文字列です。そこから、私は、与えられた1桁の短い部分文字列が何回再帰的に数回カウントされ、Nカウント<10、およびNカウント>= 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

入力が $ a、b $ 、2つの $ n $ - digit long numbersです。先頭のゼロ（瞬時に見るでしょう）。 $ c $ の最長の共通接頭辞の最長の共通接頭辞になります。 $ a、b $ 、および $ A= CA $ 、 $ b= cb $ 。

$ a= 0 ^ {n- | c |} $ と $ b= 9 ^ {n- | C |} $ $ c $ を出力するだけです（これにはspan class="math-container"> $ | c |== n $ ）

それ以外の場合は、 $ d_a $ の最初の桁の $ a $ の最初の桁であり、 $ d_b $ の最初の桁の $ b $ 。

ranges $ [A、D_A 9 ^ {| A | A | -1}] $ と $ [D_B 0 ^ {| B | -1}、b] $ 、およびprefix $ 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']