C'è un algoritmo per trovare il set più piccolo della più breve prefisso substrings di una sequenza numerica continua?

Question

Prima di tutto ciò che voglio per ringraziare in modo preventivo Dio che scende per la loro pazienza, non ho alcun background CS formale, quindi probabilmente userò alcuni di questi termini sbagliati.

Ho un puzzle: dati due numeri che definiscono un insieme di numeri di conteggio continuo dello stesso numero di cifre, tra lungo circa 5 e 12 cifre (cioè 50000 e 60000, 32325600000 e 32399999999), qual è il più veloce ed efficiente Modo per condensarlo fino a un insieme di prefissi che "contengono" tutte le permutazioni delle cifre successive?

L'approccio che abbiamo usato è un ibrido di trattarli come numeri e stringhe di carattere. Per prima cosa rimuovi qualsiasi coppia di 0 e 9 corrispondenti alla fine dell'inizio / fine. Secondo Creare la sequenza completa copiata su due colonne, in cui la seconda colonna è sempre una sottostringa con la cifra più a destra rimossa rispetto alla prima colonna. Da lì posso contare ricorsivamente quante volte viene visualizzata qualsiasi sottostringata di una cifra-più breve, conservare gli elementi in cui n-count <10 e dove n-count>= 10 rimuovere un'altra cifra da entrambe le colonne e ripetere.

Quello che mi chiedo è se c'è un modo più veloce e più efficiente per farlo. Le operazioni di stringa anziché la matematica sono state un'ovvia soluzione rapida, ma l'approccio generale si basa ancora di raggruppamento ricorsivo e tagliando i personaggi. Ho considerato una serie completa di prefisso e colonne di N-conteggio che tornano alla cifra più alta ma almeno istintivamente che si sente come se fosse meno efficiente del funzionamento ricorsivamente su un pool decrescente di numeri.

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

Supponiamo che l'input sia $ A, B $ , due $ n $ -Digit numeri lunghi. Permettiamo a zero principali (vedremo in un momento perché). Let $ c $ Sii il prefisso comune più lungo di $ A, B $ e lasciare $ A= CA $ , $ B= cb $ .

Se $ a= 0 ^ {n- | c |} $ e $ B= 9 ^ {n- | c |} $ Quindi emettiamo semplicemente $ c $ (questo include il caso $ | c |= n $ ).

Altrimenti, lascia che $ d_a $ essere la prima cifra di $ a $ , e lasciare $ D_B $ Sii la prima cifra di $ B $ .

Trova ricorsivamente una soluzione per le gamme $ [A, D_A 9 ^ {| A | -1}] $ e $ [D_B 0 ^ {| B | -1}, B] $ e prefisso $ c $ a tutto. Inoltre, aggiungi $ c (d_a + 1), \ ldots, c (d_b-1) $ .

Ecco un'implementazione Python non ottimizzata:

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

.

Ad esempio, se si esegue list(prefixes('50000000','55399999')), ottieni la seguente output: ['50', '51', '52', '53', '54', '550', '551', '552', '553']