如何避免生成单词全排列算法中的RangeError？

我基于React开发了一款同义词库应用，能从在线词典API拉取数据，用户搜索单词时会以可折叠列表展示释义、同义词和反义词。现在想加个功能展示搜索单词的所有合法变位词（不过这不是当前核心问题）。

我写了一个递归算法来生成输入单词的所有排列，但输入单词长度超过6个字母时会触发RangeError。我知道算法逻辑能找出长单词的所有排列，但受限于调用栈的最大容量。

我试过多种非递归算法，大多都遇到同样问题，只有一个可行。不过我更想重构自己的方案，而不是直接用现成的。下面是我的解决方案和找到的可行方案：

我的递归解决方案 #

/* 下面两个辅助函数可以忽略，只是出于完整性附上。它们用来计算输入单词的总排列数，
以此确定递归的终止条件，和当前问题核心无关 */

// 辅助函数1：检查字符串是否有重复字符，有则返回字符计数对象，无则返回false
const hasDuplicates = (str) => {
  const letters = {};
  str.split('').forEach(letter => {
    if (letters[letter] !== undefined) letters[letter]++;
    if (letters[letter] === undefined) letters[letter] = 1;
  });

  for (let key in letters) {
    let currLetter = letters[key];
    if (currLetter > 1) return letters;
  };

  return false;
};

// 辅助函数2：计算排列总数
const numPermutations = (str) => {
  if (hasDuplicates(str) === false) {
    let multiplier = 1;

    for (let i = 1; i <= str.length; i++) multiplier *= i;

    return multiplier;
  };

  const letters = hasDuplicates(str);
  let multiplier = 1;
  let divisor = 1;
  let visited = new Set();

  for (let i = 1; i <= str.length; i++) {
    let currLetter = str[i];

    if (letters[currLetter] > 1 && !visited.has(currLetter)) {
      for (let j = 1; j <= letters[currLetter]; j++) {
        divisor *= j;
      };
      visited.add(currLetter);
    };
    multiplier *= i;
  };

  return (multiplier / divisor);
};

// 核心递归排列函数
const permutations = (string, finalArray = [], i = 0, visited = new Set()) => {
  // 处理两个相同字符的特殊情况
  if (string.length === 2) {
    if (string.split('')[0] === string.split('')[1]) {
      finalArray.push(string);
      return finalArray;
    };
  };

  if (string.length <= 2 && finalArray.length === string.length) return finalArray;

  // 获取最大排列数，作为递归终止条件
  const maxPermutations = numPermutations(string);
  if (i === maxPermutations) return finalArray;

  const splitString = string.split('');

  // 随机打乱字符串字符
  for (let i = splitString.length - 1; i > 0; i--) {
    let randNum = Math.floor(Math.random() * (i + 1));
    let replacement = splitString[i];

    splitString[i] = splitString[randNum];
    splitString[randNum] = replacement;
  };

  if (!visited.has(splitString.join(''))) {
    // 如果当前排列未存在，加入结果数组和已访问集合，递归并递增计数
    finalArray.push(splitString.join(''));
    visited.add(splitString.join(''));

    return permutations(string, finalArray, i += 1, visited);
  };

  // 如果当前排列已存在，直接递归不递增计数
  return permutations(string, finalArray, i, visited);
};

这个方案对长度≤6的单词有效，但更长的单词会触发栈溢出。

找到的可行非递归方案 #

function permutes(string) {
  var s = string.split('').sort();
  var res = [s.join('')]
  while(true) {

    var j = s.length - 2;
    while (j != -1 && s[j] >= s[j + 1])
      j--;
    if(j == -1)
      break;
      
    var k = s.length - 1;
    while(s[j] >= s[k])
      k--;
    
    [s[j], s[k]] = [s[k], s[j]];
    var l = j + 1, r = s.length - 1;
    while (l<r) {
      [s[l], s[r]] = [s[r], s[l]];
      l++;
      r--;
    }
    res.push(s.join(''));
  }
  return res;
}

我不理解这个方案的原理，但知道它能处理长单词。不过我更倾向于重构自己的代码，而非直接使用它。

重构思路：把递归改成迭代 #

你的递归方案本质是通过随机打乱+去重来生成排列，问题出在每次生成新排列都要递归调用，长单词的排列数极多（比如7个不同字母有5040种排列），递归深度会远超调用栈上限。

要重构，核心是把递归逻辑改成循环迭代：

1. 保留原有的numPermutations计算总排列数，作为循环终止条件
2. 把递归里的状态（finalArray、visited、计数i）放到循环外部维护
3. 把递归体里的随机打乱、去重、添加逻辑放到循环内部执行

重构后的代码示例：

const hasDuplicates = (str) => {
  const letters = {};
  str.split('').forEach(letter => {
    letters[letter] = (letters[letter] || 0) + 1;
  });

  for (let key in letters) {
    if (letters[key] > 1) return letters;
  };

  return false;
};

const numPermutations = (str) => {
  if (!hasDuplicates(str)) {
    let multiplier = 1;
    for (let i = 1; i <= str.length; i++) multiplier *= i;
    return multiplier;
  };

  const letters = hasDuplicates(str);
  let multiplier = 1;
  let divisor = 1;
  let visited = new Set();

  for (let i = 1; i <= str.length; i++) {
    const currLetter = str[i-1]; // 修正原代码的索引bug：原代码用str[i]，i从1开始会漏第一个字符
    if (letters[currLetter] > 1 && !visited.has(currLetter)) {
      let factorial = 1;
      for (let j = 1; j <= letters[currLetter]; j++) factorial *= j;
      divisor *= factorial;
      visited.add(currLetter);
    };
    multiplier *= i;
  };

  return multiplier / divisor;
};

const permutations = (string) => {
  const finalArray = [];
  const visited = new Set();
  const maxPermutations = numPermutations(string);

  // 处理两个相同字符的特殊情况
  if (string.length === 2 && string[0] === string[1]) {
    finalArray.push(string);
    return finalArray;
  }

  // 处理短单词的普通情况
  if (string.length <= 2) {
    finalArray.push(string);
    finalArray.push(string.split('').reverse().join(''));
    return [...new Set(finalArray)]; // 去重，比如两个相同字符的情况
  }

  // 循环迭代生成所有排列
  while (finalArray.length < maxPermutations) {
    const splitString = string.split('');
    // 随机打乱字符
    for (let i = splitString.length - 1; i > 0; i--) {
      const randNum = Math.floor(Math.random() * (i + 1));
      [splitString[i], splitString[randNum]] = [splitString[randNum], splitString[i]];
    }
    const perm = splitString.join('');
    if (!visited.has(perm)) {
      visited.add(perm);
      finalArray.push(perm);
    }
  }

  return finalArray;
};

关键改进点 #

• 把递归改成while循环，避免调用栈溢出
• 修正了原numPermutations里的索引bug（原代码用str[i]，i从1开始会漏掉第一个字符）
• 简化了字符计数的逻辑（letters[letter] = (letters[letter] || 0) + 1）
• 直接用finalArray.length判断是否达到总排列数，不需要额外的计数变量i

注意事项 #

这种随机打乱+去重的方式，在单词很长且重复字符少的情况下，可能会出现大量重复尝试（比如生成已存在的排列），效率不如找到的那个非递归方案（它是按字典序生成排列，无重复、无冗余）。但如果坚持用自己的思路，这个迭代版本可以解决栈溢出问题。

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