Esercizio su ordinamento lessicografico

[JoKeRxbLaCk93]

Ciao a tutti, ho questo esercizio che purtroppo non so risolvere:
Si consideri l'alfabeto di simboli A,C,G,T. Si dia quindi la posizione nell'ordinamento lessicografico della stringa AAAAT.

Pensavo che nell'ordinamento lessicografico si ha una cosa del genere:
"A", "C", "G", "T", "AA", "AC", "AG", "AT", "AAA", "AAC", "AAG", "AAT", "AAAA", "AAAC", "AAAG", "AAAT", "AAAAA", "AAAAC", "AAAAG", "AAAAT" <--- Ma è corretto questo ordinamento lessicografico? Inoltre non vi è una formula per poterlo calcolare senza dover creare tutte le stringhe a mano?

Grazie mille,

[vict85]

Quell'ordinamento lessicografico è sbagliato, se con lessicografico intendi l'ordine che i matematici chiamano così. E non vedo come tu possza darne una posizione dato che è dopo tutte le stringhe che iniziano con AAAAA, AAAAC e AAAAG.

D'altra parte guardando su wiki ho visto che tu stai in realtà usando questo ordine https://en.m.wikipedia.org/wiki/Shortlex_order

[JoKeRxbLaCk93]

"vict85":Quell'ordinamento lessicografico è sbagliato, se con lessicografico intendi l'ordine che i matematici chiamano così. E non vedo come tu possza darne una posizione dato che è dopo tutte le stringhe che iniziano con AAAAA, AAAAC e AAAAG.

D'altra parte guardando su wiki ho visto che tu stai in realtà usando questo ordine https://en.m.wikipedia.org/wiki/Shortlex_order

Siccome il testo dell'esercizio dice di ordinarlo in modo lessicografico allora sicuramente ho sbagliato Quindi l'ordinamento lessicografico come è sviluppato sull'insieme A?

[vict85]

Lo trovi su wiki spiegato in modo completo. Comunque è il normale ordinamento da dizionario. Il punto però è che l'esercizio non è risolvibile con l'ordine lessicografico il numero di elementi che lo precedono ha la stessa cardinalità dell'intero linguaggio.

Forse il tuo professore usa il termine lessicografico per l'ordinamento che ho citato sopra. Ti conviene chiedere conferma ed essere però consapevole della cosa. Per lo shortlex, pensò che una formula sia possibile trovarla. Dopo che conti tutte le stringhe di lunghezza inferiore devi trovare la posizione nelle stringe della stessa lunghezza.

[JoKeRxbLaCk93]

"vict85":Lo trovi su wiki spiegato in modo completo. Comunque è il normale ordinamento da dizionario. Il punto però è che l'esercizio non è risolvibile con l'ordine lessicografico il numero di elementi che lo precedono ha la stessa cardinalità dell'intero linguaggio.

Forse il tuo professore usa il termine lessicografico per l'ordinamento che ho citato sopra. Ti conviene chiedere conferma ed essere però consapevole della cosa. Per lo shortlex, pensò che una formula sia possibile trovarla. Dopo che conti tutte le stringhe di lunghezza inferiore devi trovare la posizione nelle stringe della stessa lunghezza.

Perfetto, ora mando una mail per conferma
Nel caso in cui fosse stato l'ordinamento shortlex, la formula come si può trovare?

[JoKeRxbLaCk93]

Uppete