Skip to content

计算JavaScript数组或字符串的所有排列

作为一个开发者,我在早期的开发过程中曾经遇到过一个问题,那就是生成数组元素或字符串字符的所有排列。这是一个经典的问题,可以使用递归来解决,尽管效率可能不高。

[!WARNING]

以下实现主要是为了演示目的。如果您需要在生产环境中实现类似的功能,应考虑使用更高效的算法。由于执行时间呈指数增长,超过8到10个元素可能会导致您的环境卡住。

数组排列

使用递归,我们可以生成数组元素的所有排列,包括重复元素。递归函数的基本情况是当数组的长度等于21时。在这种情况下,我们分别返回数组本身或元素交换后的数组。

对于其他情况,我们使用Array.prototype.reduce()来迭代数组的元素,为其余元素创建所有的部分排列。然后,我们使用Array.prototype.map()将当前元素与每个部分排列组合,使用Array.prototype.reduce()将所有排列组合成一个数组。

const permutations = arr => {
  if (arr.length <= 2) return arr.length === 2 ? [arr, [arr[1], arr[0]]] : arr;
  return arr.reduce(
    (acc, item, i) =>
      acc.concat(
        permutations([...arr.slice(0, i), ...arr.slice(i + 1)]).map(val => [
          item,
          ...val,
        ])
      ),
    []
  );
};

permutations([1, 33, 5]);
// [ [1, 33, 5], [1, 5, 33], [33, 1, 5], [33, 5, 1], [5, 1, 33], [5, 33, 1] ]

字符串排列

对于字符串,可以使用类似的技巧。基本情况是相同的,算法基本上也是相同的。唯一的显著区别是使用String.prototype.split()将字符串转换为字符数组,以及使用String.prototype.join()将字符数组转换回字符串。

const stringPermutations = str => {
  if (str.length <= 2) return str.length === 2 ? [str, str[1] + str[0]] : [str];
  return str
    .split('')
    .reduce(
      (acc, letter, i) =>
        acc.concat(
          stringPermutations(str.slice(0, i) + str.slice(i + 1)).map(
            val => letter + val
          )
        ),
      []
    );
};

stringPermutations('abc'); // ['abc', 'acb', 'bac', 'bca', 'cab', 'cba']
const stringPermutations = str => {
  if (str.length <= 2) return str.length === 2 ? [str, str[1] + str[0]] : [str];
  return str
    .split('')
    .reduce(
      (acc, letter, i) =>
        acc.concat(
          stringPermutations(str.slice(0, i) + str.slice(i + 1)).map(
            val => letter + val
          )
        ),
      []
    );
};

stringPermutations('abc'); // ['abc', 'acb', 'bac', 'bca', 'cab', 'cba']