计算JavaScript数组或字符串的所有排列
作为一个开发者,我在早期的开发过程中曾经遇到过一个问题,那就是生成数组元素或字符串字符的所有排列。这是一个经典的问题,可以使用递归来解决,尽管效率可能不高。
[!WARNING]
以下实现主要是为了演示目的。如果您需要在生产环境中实现类似的功能,应考虑使用更高效的算法。由于执行时间呈指数增长,超过8到10个元素可能会导致您的环境卡住。
数组排列
使用递归,我们可以生成数组元素的所有排列,包括重复元素。递归函数的基本情况是当数组的长度等于2
或1
时。在这种情况下,我们分别返回数组本身或元素交换后的数组。
对于其他情况,我们使用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']