如何计算字符集全组合有序列表中指定字符串的零基索引？

核心思路 #

给定按字典序排序、包含字符集所有长度≤max_len的字符串的列表，可通过逐字符计算贡献+前缀计数的方式高效计算目标字符串的零基索引，无需遍历整个列表。

关键定义 #

1. 字符集映射：设字符集C为升序排列的列表（如题目中的['1','a','b']），为每个字符分配索引值v（即C[v] = 目标字符，v从0开始）。
2. 字符集大小：k = len(C)
3. 辅助函数f(n)：计算"长度从0到n的任意后缀"的总数量，即f(n) = sum_{l=0}^n k^l。
   • 当k≠1时，可简化为公式：f(n) = (k^(n+1) - 1) // (k-1)
   • 当k=1时（字符集仅含一个字符），f(n) = n+1
4. 目标字符串：设目标字符串为s，长度为m；若m > max_len或s包含字符集外的字符，则s不在列表中。

计算公式 #

目标字符串s的零基索引为：

index = sum( v_i * f(max_len - (i+1)) for i, v_i in enumerate(s) ) + m

公式解释 #

• 逐字符贡献项：v_i * f(max_len - (i+1))
  • v_i是字符s[i]在字符集中的索引，代表有v_i个字符比s[i]小；
  • f(max_len - (i+1))是每个小于s[i]的字符后可跟随的后缀数量（后缀长度从0到max_len - (i+1)，对应总字符串长度从i+1到max_len）；
  • 两者相乘表示：所有前i位与s一致、第i位字符小于s[i]的字符串总数。
• 前缀计数项：+m
  代表所有s的真前缀（包括空串）的数量，这些前缀的字典序均小于s，共有m个（空串、长度1的前缀、...、长度m-1的前缀）。

示例验证 #

以题目中的字符集['1','a','b']、max_len=3为例：

1. 计算s="a"：
   • m=1，v0=1
   • sum = 1 * f(3-1) =1*(1+3+9)=13
   • index=13+1=14，与题目示例一致。
2. 计算s="ab"：
   • m=2，v0=1，v1=2
   • sum=1*f(2)+2*f(1)=13+2*(1+3)=21
   • index=21+2=23，与题目示例一致。
3. 计算s="ba1"：
   • m=3，v0=2，v1=1，v2=0
   • sum=2*f(2)+1*f(1)+0*f(0)=26+4+0=30
   • index=30+3=33，与题目示例一致。

代码实现（Python） #

def compute_index(charset, max_len, s):
    k = len(charset)
    if k == 0:
        return 0 if s == "" else -1
    
    char_to_idx = {char: idx for idx, char in enumerate(charset)}
    # 检查字符是否属于字符集
    for char in s:
        if char not in char_to_idx:
            return -1
    m = len(s)
    if m > max_len:
        return -1
    
    def f(n):
        if n < 0:
            return 0
        if k == 1:
            return n + 1
        return (k ** (n + 1) - 1) // (k - 1)
    
    total = 0
    for i, char in enumerate(s):
        v_i = char_to_idx[char]
        total += v_i * f(max_len - (i + 1))
    total += m
    return total

注意事项 #

• 字符集必须升序排列，否则字符索引映射错误会导致计算结果偏差；
• 若目标字符串长度超过max_len或包含字符集外的字符，返回-1表示无效；
• 当k=1时（字符集仅一个字符），公式依然适用，此时列表为""、"c"、"cc"、...、"c"*max_len。

内容的提问来源于stack exchange，提问作者JacobMoon