时间戳

首页 > 解决方案 > 如何在 JavaScript 中为一组字母（小写和大写）实现排列生成器（或记忆函数）？

javascript - 如何在 JavaScript 中为一组字母（小写和大写）实现排列生成器（或记忆函数）？

问题描述

我正在实现一个变量名生成器，我无法控制所需的变量名的数量，并且认为，使用生成器或记忆函数是要走的路，而不是创建所有排列的列表并保存在内存中.

基本上，我想创建一个以增量方式产生所有排列[a-z][A-Z]的函数。它应该返回如下序列{'a', 'b', ...,'z','aa','ab',....,'az', 'ba', .... 'aA',... 'aTr'...'ZZZ', ...'Z(*52)'}

现在我有，

function* varNameGenerator() {
  const all =
    'abcdefghijklmnopqrstuvwxyz' + 'abcdefghijklmnopqrstuvwxyz'.toUpperCase();
  let prefix = '';
  for (let i = 0; i < all.length; i++) {
    for (let j = 0; j < all.length; j++) {
      yield prefix + all[j];
    }
    prefix += all[i];
  }
}

这有助于生成2705结果，因为输出将是集合中的一个序列{'a', 'b', ...,'aa',...'aZ', 'aba','abb'....,'abZ','abca','abcb','abcc',...,'abcZ','abcda'...}，依此类推。这是可用的，但变量名称的长度增加得非常快（每 52 个函数调用）。

那么是否有一种实现可以首先产生最小长度的字母表的所有排列？

标签： javascriptalgorithmperformance

解决方案

您可以使用递归生成器：

     const ALPHABET = 'abcdefghijklmnopqrstuvwxyz' + 'abcdefghijklmnopqrstuvwxyz'.toUpperCase();

    function* nameGenerator(length = 30, prev = "") {
      if(length <= 0) {
        yield prev;
        return;
      }

      for (const char of ["", ...ALPHABET]) {
        yield* nameGenerator(length - 1, prev + char);
      }
    }
   
    const it = nameGenerator();

    for(let i = 0; i < 100; i++)
      console.log(it.next().value);

这个怎么运作：

  1. prev进行了 30 次递归调用，每个调用都向("" 在第一次迭代中)添加一个字符：

    "" -> "" + "" -> ... -> "" + ... + ""

  2. 最上面的迭代器返回该值

                 <-- ""

然后最上面的循环转到下一个字符“a”，并返回它，这发生在所有字符上：

                      -> "" + ... + "a"
                     <-- "a"
                     ...
                     -> "" + ... + "Z"
                     <--- "Z"

  1. 循环完成，我们上一层并继续循环，然后再上一层回到循环：

                     <-
    "" + ... + "a" -> "" + ... + "a" + "a"
                 <-- "aa" 
                 <-- "ab"
                 ....
                 <-- "aZ"

这一直持续到我们在最底层循环 30 次

推荐阅读