algorithm - 如何优雅且命令式地生成字母表的第 n 个字符串？

Question

给定一个字母表，例如:["a","b","c","d"] , 由该字母表的字符组成的所有字符串的顺序是:

""
"a"
"b"
"c"
"d"
"aa"
"ab"
"ac"
...

Haskell 可以优雅地递归地生成该序列的第 n 个元素:

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

但这是低效的。使用基本转换，您可以尝试强制生成它(使用 JavaScript 仅用于演示):

function nth(n) {
  var str = "";
  while (n > 0) {
    str += String.fromCharCode(97 + n % 4);
    n = Math.floor(n / 4);
  }
  return str;
};

for (var i = 0; i < 64; ++i) {
  console.log(nth(i));
}

但这实际上会生成以下序列:

""
"b"
"c"
"d"
"ab"
"bb"
"cb"
"db"
"ac"
"bc"
"cc"
"dc"
"ad"
"bd"
"cd"
"dd"
"aab"

这不是我们想要的:注意缺少的“a”、“aa”、“ba”等。我可能缺少一些简单的操作来修复命令式实现，因此，我的问题是:有没有强制生成第 n 个字母表字符串的优雅方式？

Answer 1

在 while 循环的开头插入 n--。如果您希望结果按字典顺序排列，请在打印前反转字符串。