将字符串映射到保持字典顺序的数字 [英] Map strings to numbers maintaining the lexicographic ordering

问题描述

我正在寻找一种能够将字符串映射到数字的算法或函数，其结果值与字符串的字典顺序相对应.示例:

I'm looking for an algorithm or function that is able to map a string to a number in such way that the resulting values correspond the lexicographic ordering of strings. Example:

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

作为一个函数，它应该是这样的:f(x) = y，所以对于任何 x1 <x2 => f(x1)

As a function it should be something like: f(x) = y, so that for any x1 < x2 => f(x1) < f(x2), where x is an arbitrary string and y is a number.

如果 x 的输入集是有限的，那么我总是可以进行排序并分配适当的值，但我正在寻找一些通用的东西，用于 x 的无限输入集.

If the input set of x is finite, then I could always do a sort and assign the proper values, but I'm looking for something generic for an unlimited input set for x.

推荐答案

如果你要求 f 映射到整数，这是不可能的.

If you require that f map to integers this is impossible.

假设有这样一个地图f.考虑字符串 a、aa、aaa 等.考虑值 f(a)、f(aa)、f(aaa) 等.因为我们要求 f(a) 我们看到 f(a_n) 趋于无穷，而 n 趋于无穷；这里我使用了一个明显的符号，即 a_n 是字符 a 重复了 n 次.现在考虑字符串 b.我们要求 f(a_n) 用于所有 n.但是 f(b) 是一些有限整数，我们刚刚展示了 f(a_n) 趋于无穷大.我们有一个矛盾.不可能有这样的地图.

Suppose that there is such a map f. Consider the strings a, aa, aaa, etc. Consider the values f(a), f(aa), f(aaa), etc. As we require that f(a) < f(aa) < f(aaa) < ... we see that f(a_n) tends to infinity as n tends to infinity; here I am using the obvious notation that a_n is the character a repeated n times. Now consider the string b. We require that f(a_n) < f(b) for all n. But f(b) is some finite integer and we just showed that f(a_n) goes to infinity. We have a contradiction. No such map is possible.

也许你可以告诉我们你需要这个做什么?这是相当抽象的，我们也许可以提出更合适的建议.此外，不必担心一般地解决它".YAGNI 等等.

Maybe you could tell us what you need this for? This is fairly abstract and we might be able to suggest something more suitable. Further, don't necessarily worry about solving "it" generally. YAGNI and all that.

这篇关于将字符串映射到保持字典顺序的数字的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！