JavaScript如何实现元素全排列实例代码

时间:2021-05-26

排列 (Permutation / Arrangement)

概念

n 个不同元素中任意选取 m (m <= n) 个元素进行排列,所有排列情况的个数叫做 排列数,其值等于:

A = n! / (n - m)!

! 表示数学中的阶乘运算符,可以通过以下函数实现:

function factorial(n) { if (n === 0 || n === 1) { return 1; } else if (n < 0) { return null; } else { return n * factorial(n - 1); }}console.log(factorial(4)); // 24

当 n = m 时,称为 全排列,其值等于:

A = n!

全排列相当于将所有元素进行排序,得到所有不同顺序情况的个数;

分析

利用阶乘函数,通过上述数学公式只能得到所有情况的个数值,不容易得到具体的每种情况,要获取每种情况的输出值的话需要另寻他法;

用数组举例分析:

全排列:

[1, 2, 3] => [
[1, 2, 3],
[1, 3, 2],
[2, 1, 3],
[2, 3, 1],
[3, 1, 2],
[3, 2, 1]
]

共 6 种情况

树状图表示:

1 2 3
/ \ / \ / \
2 3 1 3 1 2
| | | | | |
3 2 3 1 2 1 => 6

3 个元素中选取 2 个时:(n = 3, m = 2)

[1, 2, 3] => [
[1, 2],
[1, 3],
[2, 1],
[2, 3],
[3, 1],
[3, 2]
]

共 6 种情况

树状图表示:

1 2 3
/ \ / \ / \
2 3 1 3 1 2 => 6

实现

let arr = [1, 2, 3];function permutation(a, m) { // 保存最终输出结果 let result = []; // 定义 m 值默认等于 n,即全排列 let n = a.length; m = m || n; // 定义递归函数保存结果到数组中 // _a 为输入数组, // tmpResult 为保存单个情况结果的数组 function recur(_a, tmpResult = []) { if (tmpResult.length === m) { // 结果达到 m 个时保存结果, // 停止递归并进入下一次遍历 result.push(tmpResult); } else { for (let i = 0; i < _a.length; i++) { // 复制一份输入数组,防止引用值被改变 let tmpA = _a.concat(); // 复制一份保存结果的数组,防止每次遍历相互影响 let _tmpResult = tmpResult.concat(); // 保存当前遍历值 _tmpResult.push(tmpA[i]); // 删除当前遍历值,传递参数进入下一层递归 tmpA.splice(i, 1); recur(tmpA, _tmpResult); } } } // 开始执行递归,然后返回最后结果 recur(a); return result;}console.log(permutation(arr));// 3 个数全排列:console.log(permutation(arr, 2));// 3 个数中选取 2 个数排列:

最终实现函数就是 permutation(a, m),其中参数 a 为输入数组,包含需要排列的所有元素,参数 m 为选取需要排列的个数,默认等于输入数组的长度,即默认全排列,注意 m 不能大于元素个数;

拓展

以上函数输出值为一个二维数组,如果需要便于观察,输出一个一维数组,可以定义一个合并函数:

function merge(arr) { return arr.map(x => x.join(''));}let result = merge(permutation([1, 2, 3]));console.log(result);// [123, 132, 213, 231, 312, 321]

总结

以上就是这篇文章的全部内容了,希望本文的内容对大家的学习或者工作具有一定的参考学习价值,谢谢大家对的支持。

声明:本页内容来源网络,仅供用户参考;我单位不保证亦不表示资料全面及准确无误,也不保证亦不表示这些资料为最新信息,如因任何原因,本网内容或者用户因倚赖本网内容造成任何损失或损害,我单位将不会负任何法律责任。如涉及版权问题,请提交至online#300.cn邮箱联系删除。

相关文章