如何优雅且命令式生成字母表序列中的第n个字符串？

假设我们有一个字母表，比如 ["a","b","c","d"]，所有由它的字符组成的字符串会按这样的顺序排列：""、"a"、"b"、"c"、"d"、"aa"、"ab"、"ac"…… 要找到这个序列的第n个元素，Haskell里有个很优雅的递归写法，但它的效率却不太行，我们可以用进制转换的思路，用命令式的方式优化实现。

Haskell的递归实现：优雅但低效 #

先看Haskell里的实现，代码非常简洁：

nth :: Int -> String
nth n = reverse $ alphabet !! n
  where alphabet = [""] ++ concatMap (\ str -> map (: str) "abcd") alphabet

这个思路很直观：alphabet一开始只有空字符串，之后不断把每个已有的字符串前面加上字母表的每一个字符，生成新的字符串并拼接到序列里。比如第一次扩展会得到"a"、"b"、"c"、"d"，第二次扩展每个这些字符串，得到"aa"、ba、ca、da、ab、bb…… 最后取第n个元素时反转一下，因为生成的时候是把新字符加在前面的。

但这种方式的问题也很明显：每次获取第n个元素都要从头构建整个序列，而且序列是无限的，n越大，访问速度越慢，完全不适合处理较大的n值。

进制转换优化：JavaScript命令式实现 #

其实这个序列的排列规律和进制数非常像，我们可以把它看成是以字母表长度为基数的特殊进制数——唯一的区别是空字符串对应n=0，剩下的数字从1开始对应序列的元素。具体的实现思路是：

1. 先处理特殊情况：n=0直接返回空字符串；
2. 把n减1，抵消空字符串占的位置；
3. 通过循环对数字取余，得到当前位对应的字母索引，然后把数字除以基数再减1，直到数字小于0；
4. 把收集到的字母反转（因为取余得到的是从低位到高位的字符），拼接成最终字符串。

对应的JavaScript代码如下：

function nth(n, alphabet = ['a', 'b', 'c', 'd']) {
  if (n === 0) return '';
  const base = alphabet.length;
  let num = n - 1;
  const result = [];
  
  do {
    result.push(alphabet[num % base]);
    num = Math.floor(num / base) - 1;
  } while (num >= 0);
  
  return result.reverse().join('');
}

举几个例子验证一下：

• n=0 → 返回""，正确；
• n=1 → num=0，取余0得到"a"，num变为-1，反转后是"a"，正确；
• n=5 → num=4，第一次取余0得到"a"，num变为0；第二次取余0得到"a"，num变为-1；反转后是"aa"，正确；
• n=4 → num=3，取余3得到"d"，num变为-1，结果是"d"，正确。

这种方式的效率要高得多，不管n多大，都只需要循环log_base(n)次，直接计算出结果，不需要构建整个序列。

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