algorithm - 如何计算包含一组字符的所有可能组合的排序列表中字符串值的索引？

Question

给定一个按字典顺序排序的列表，其中包含一组字符到最大长度的所有可能组合，如何计算特定字符串值的索引？

例如，如果字符集为“1”、“a”和“b”，最大字符串长度为 3，则所有可能组合的排序列表将为:

 0: ""        10: "1b"      20: "aa1"     30: "b1a"
 1: "1"       11: "1b1"     21: "aaa"     31: "b1b"
 2: "11"      12: "1ba"     22: "aab"     32: "ba"
 3: "111"     13: "1bb"     23: "ab"      33: "ba1"
 4: "11a"     14: "a"       24: "ab1"     34: "baa"
 5: "11b"     15: "a1"      25: "aba"     35: "bab"
 6: "1a"      16: "a11"     26: "abb"     36: "bb"
 7: "1a1"     17: "a1a"     27: "b"       37: "bb1"
 8: "1aa"     18: "a1b"     28: "b1"      38: "bba"
 9: "1ab"     19: "aa"      29: "b11"     39: "bbb"

如何有效地计算“a”、“ab”或“ba1”的从零开始的索引？

Answer 1

首先，您需要一种方法来计算这样的列表中有多少个字符串。

设 count(n) 为长度 <= n 的字符串数量。有很多方法可以计算:

• 递归:count(n) = 1 + 3 * count(n-1)
• 长度总和:count(n) = sum_from_0_to_n(3ⁿ)
• 公式:count(n) = (3ⁿ⁺¹-1)/2

然后，使用 count(n)，很容易递归地找到任何字符串的索引。

令index(s,n)为s在长度<=n的字符串列表中的索引，并令s.tail为s删除第一个字符:

• 如果 s == ""，则索引(s,n) = 0
• 如果 s == "1..."则索引(s,n) = 1 + 索引(s.tail, n-1)
• 如果 s == "a..."则索引(s,n) = 1 + 计数(n-1) + 索引(s.tail, n-1)
• 如果 s == "b..."则索引(s,n) = 1 + 2 * 计数(n-1) + 索引(s.tail, n-1)

查看 count(n) 的递归公式，并注意这些选择将 count(n) 分为 4 部分。