將整數映射到給定字符串空間中的字符串

假設我有一個字母'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

將整數映射到給定字符串空間中的字符串

回答

相關問題