文章出自个人博客 https://knightyun.github.io/2019/05/11/js-permutation,转载请申明。
元素在地壳中的含量排序,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];/*
参数 a 为输入数组,
元素个数 n 为 a 的长度,
选取个数为 m;
*/
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 个数全排列:
/*
[ [1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]
]
*/console.log(permutation(arr, 2));
// 3 个数中选取 2 个数排列:
/*
[ [1, 2], [1, 3], [2, 1], [2, 3], [3, 1], [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]
版权声明:本站所有资料均为网友推荐收集整理而来,仅供学习和研究交流使用。
工作时间:8:00-18:00
客服电话
电子邮件
admin@qq.com
扫码二维码
获取最新动态