将整数映射到给定字符串空间中的字符串

假设我有一个字母'abcd'和最大字符串长度为3.这给我85 possible strings，包括空字符串。我想要做的是将范围[0,85）内的整数映射到字符串空间中的字符串，而不使用查找表。事情是这样的：将整数映射到给定字符串空间中的字符串

0 => '' 
1 => 'a' 
... 
4 => 'd' 
5 => 'aa' 
6 => 'ab' 
... 
84 => 'ddd'

这是很简单的做，如果字符串是使用此伪算法固定长度：

str = '' 
for i in 0..maxLen do 
    str += alphabet[i % alphabet.length] 
    i /= alphabet.length 
done

我想不通，虽然做的不错的，有效的方法当字符串的长度可以在[0,3）范围内的任何位置。这将在随机输入的紧密循环中运行，所以我想避免任何不必要的分支或查找。

来源

2012-02-14 spencercw

将您的索引移动一个，并暂时忽略空字符串。所以你会映射0 -> "a", ..., 83 -> "ddd"。

然后映射是

n -> base-4-encode(n - number of shorter strings)

随着26个符号，这就是Excel的列编号方案。

使用s符号，有s + s^2 + ... + s^l非空字符串长度最多l。撇开微不足道的情况s = 1，那个总和是（几何系列的部分总和）s*(s^l - 1)/(s-1)。

因此，鉴于n，找到最大的l使得s*(s^l - 1)/(s-1) <= n，即

l = floor(log((s-1)*n/s + 1)/log(s))

然后让m = n - s*(s^l - 1)/(s-1)和编码m如碱s一个l+1码元串（ 'A' 〜> 0，b位'〜> 1，...）。

对于包含空字符串的问题，将0映射到空字符串，对于n > 0编码n-1如上所述。

来源

2012-02-14 20:53:59

您的掌握所涉及的数学显然比我的要强很多，但这正是我所期待的;它完美地工作。非常感谢您的帮助。 – spencercw 2012-02-14 21:31:25

找出每个长度的字符串数量：N0，N1，N2 & N3（实际上，您不需要N3）。然后，使用这些值来划分整型空间：0..N0-1是长度0，N0..N0 + N1-1是长度1，等等。在每个分区中，您可以使用您的固定长度算法。

最糟糕的是，您已经大大缩小了查找表的大小。

来源

2012-02-14 20:52:43

这里是一个C＃的解决方案：

static string F(int x, int alphabetSize) 
    { 
     string ret = ""; 
     while (x > 0) 
     { 
      x--; 
      ret = (char)('a' + (x % alphabetSize)) + ret; 
      x /= alphabetSize; 
     } 

     return ret; 
    }

如果你想进一步优化这一点，你可能需要做一些事情来避免字符串连接。例如，您可以将结果存储到预分配的char []数组中。

来源

2012-02-14 21:22:28

在Haskell

encode cs n = reverse $ encode' n where 
    len = length cs 
    encode' 0 = "" 
    encode' n = (cs !! ((n-1) `mod` len)) : encode' ((n-1) `div` len)

检查：

*主要>图（编码 “ABCD”）[0 ..84“[”“a”，“b”，“c”，“d”，“aa”，“ab”，“ac”，“ad”，“ba”，“bb”，“bc”， “BD”， “CA”， “CB”， “CC”， “CD”， “DA”， “DB”， “DC”， “DD”， “AAA”， “AAB”， “AAC”，“AAD ”， “阿坝”， “羊毛”， “ABC”， “ABD”， “ACA”， “ACB”， “ACC”， “ACD”， “反倾销协定”， “亚行”， “ADC”， “添加”， “咩”， “巴布”， “BAC”， “坏”， “BBA”， “BBB”， “BBC”， “BBD”， “BCA”， “BCB”， “BCC”， “BCD”，“BDA ”， “BDB”， “BDC”， “BDD”， “民航局”， “出租车”， “CAC”， “CAD”， “CBA”， “CBB”， “CBC”， “生物多样性公约”， “CCA”， “建行”， “CCC”， “CCD”， “综合发展区”， “国家开发银行”， “CDC”， “CDD”， “DAA”， “轻拍”， “DAC”， “爸爸”， “DBA”，“DBB “”dbc“”dbd“dca”dcb“dcc”dcd“dda”ddb“ddc”ddd“]

来源

2012-02-14 21:40:17

将整数映射到给定字符串空间中的字符串

回答

相关问题