Algoritmo: stampa dell'indice corretto per la sequenza di caratteri

Question

Mi sono imbattuto nel seguente problema mentre preparavo un esame:

Immagina un alfabeto di parole. Esempio:

a ==> 1 
b ==> 2 
c ==> 3 
... 
z ==> 26 
ab ==> 27 
ac ==> 28 
... 
az ==> 51 
bc ==> 52 
and so on. 

La sequenza di caratteri deve essere in ordine ascendente solo (cioè 'ab' è valido ma 'ba' non è).

Domanda: con qualsiasi parola, stampa il suo indice se valido e 0 se non lo è.

Input Output 
ab 27 
ba 0 
aez 441 

Qualsiasi suggerimento su come risolvere questo sarebbe apprezzato.

Answer 1

Permettetemi di darvi alcuni suggerimenti:

• si può trovare un formula per il numero di tali parole di una determinata lunghezza k?
• Ora fissare una lunghezza k e una lettera l. Quante parole di lunghezza k iniziano con l?

Suggerimento: triangolo Pascal. Se hai bisogno di qualche suggerimento in più, http://en.wikipedia.org/wiki/Combinadic può aiutarti. Se hai bisogno di qualche implementazione, puoi trarre ispirazione dalla funzione rank definita in (linguaggio Python) https://github.com/sagemath/sagelib/blob/master/sage/combinat/choose_nk.py

Answer 2

1. assicurarsi che l'input sia solo lettere. Fallire se non.
2. Impostare un ciclo in base alla lunghezza della stringa meno 1.
3. "Sottrarre" il valore della prima lettera nella stringa dal successivo. Se il valore è zero o positivo, viene eseguito poiché la stringa non è crescente, quindi restituisce 0.
4. Ripetere spostando la stringa una lettera alla volta per controllare la lettera successiva.
5. Se si arriva alla fine, si tratta di una stringa di ordine crescente.

Per essere onesti, non ho menzionato un algoritmo su come calcolare il valore dell'indice, solo il caso di uscita. Ma ti dà un inizio nella giusta direzione e il calcolo dell'indice seguirà lo stesso schema.

Ulteriori informazioni:

Inizio contando verso l'alto sulla prima lettera. Quando premi 'z', ripristina la stringa successiva e continua a contare -> "aa" fallisce non contarlo. Aggiungi al prossimo che qui è "ab". Dopo aver premuto "az", prova "ba" - fallire, continua ad aggiungere lettere finché non ottieni una stringa valida "bc" e ricomincia a contare. È come un contachilometri che conta verso l'alto.

Dang lento, ma dovrebbe funzionare in quanto è ciò che si fa manualmente per ottenere la risposta.

A proposito, c'è una soluzione molto più elegante accennato da @hivert che sarebbe quasi istantanea per il calcolo ...