Tracer des chaînes de caractères vers des nombres en conservant l'ordre lexicographique.

Question

Je cherche un algorithme ou une fonction capable de faire correspondre une chaîne de caractères à un nombre de telle sorte que les valeurs résultantes correspondent à l'ordre lexicographique des chaînes de caractères. Exemple :

"book" -> 50000
"car"  -> 60000
"card" -> 65000
"a longer string" -> 15000
"another long string" -> 15500
"awesome" -> 16000

En tant que fonction, elle devrait être du type : f(x) = y, de sorte que pour tout x1 < x2 => f(x1) < f(x2), où x est une chaîne de caractères arbitraire et y un nombre.

Si l'ensemble des entrées de x est fini, alors je pourrais toujours faire un tri et assigner les valeurs appropriées, mais je cherche quelque chose de générique pour un ensemble d'entrées de x illimité.

Answer 1

J'ai posé une question ici Que signifie l'ordre lexicographique ? Comme solution de contournement, vous pouvez ajouter des symboles vides avec le code zéro à la droite de la chaîne, et utiliser l'expansion du cas II.

Sans une telle expansion avec des symboles vides supplémentaires, je ne sais pas comment faire une telle cartographie.... Mais si vous avez un ensemble fini de symboles (V), alors |V*| est équivalent à |N| -- fait tiré de Disrete Math.