هل هناك خوارزمية للعثور على أصغر مجموعة من أقصر سلاسل فرعية بادئة لتسلسل رقمي مستمر?

Question

قبل أي شيء أريد أن أشكر بشكل استباقي أي شخص يسقط من قبل لصبرهم, ليس لدي أي خلفية كس الرسمية لذلك أنا على الارجح الى استخدام بعض هذه المصطلحات خاطئة.

لدي لغز:نظرا رقمين التي تحدد مجموعة من أرقام العد المستمر من نفس العدد من الأرقام, بين تقريبا 5 و 12 أرقام طويلة (أي 50000 و 60000, 32325600000 و 32399999999), ما هي الطريقة الأسرع والأكثر فعالية لتكثيف هذا وصولا الى مجموعة من البادئات التي "تحتوي على" جميع التباديل من الأرقام اللاحقة?

النهج الذي استخدمناه هو مزيج من التعامل مع هذه الأرقام وسلاسل الأحرف.أولا إزالة أي أزواج من مطابقة 0 و 9 في نهاية بداية / نهاية.ثانيا ، قم بإنشاء التسلسل الكامل المنسوخ إلى عمودين ، حيث يكون العمود الثاني دائما سلسلة فرعية مع إزالة الرقم الموجود في أقصى اليمين بالنسبة إلى العمود الأول.من هناك يمكنني أن أحسب بشكل متكرر عدد المرات التي يحدث فيها أي سلسلة فرعية أقصر من رقم واحد ، احتفظ بالعناصر حيث ن-عد<10 ، وأين ن-العد> = 10 قم بإزالة رقم آخر من كلا العمودين وكرر.

ما أتساءل هو ما إذا كانت هناك طريقة أسرع وأكثر كفاءة للقيام بذلك.كانت عمليات السلسلة بدلا من الرياضيات حلا سريعا واضحا ، لكن النهج العام لا يزال يعتمد على التجميع المتكرر وتقطيع الأحرف.لقد فكرت في جعل سلسلة كاملة من البادئة و ن العد الأعمدة التي تعود إلى أعلى رقم ولكن على الأقل غريزي أن يشعر وكأنه سيكون أقل كفاءة من التشغيل بشكل متكرر على مجموعة متناقص من الأرقام.

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 أ ، ب$, ، اثنان $n$- أرقام أرقام طويلة.نسمح الأصفار الرائدة (سنرى في لحظة لماذا).دعونا $c$ كن أطول بادئة شائعة لـ a أ ، ب$, ، والسماح a أ = كا cA, b ب = سب$.

إذا A أ = 0^{ن - / ج/}} و B ب = 9^{ن - / ج/}} ثم نحن ببساطة الإخراج $c$ (وهذا يشمل القضية c / ج/ = ن n).

خلاف ذلك ، دعونا d د_أa كن الرقم الأول من $A$, ، والسماح d د_ب$ كن الرقم الأول من $B$.

العثور بشكل متكرر على حل للنطاقات A [أ ، د_أ 9^{/أ / -1}]] و d [د_ب 0^{/ب / -1} ، ب]], ، والبادئة $c$ إلى كل شيء.أيضا ، إضافة c ج (د_أ+1)، \ لدوتس ، ج (د_ب-1)).

هنا هو تنفيذ بيثون غير الأمثل:

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