排列
排列概念
从m个不同元素中，任取n(n<=m)个元素按照一定的顺序排成一列，叫做从m个不同元素中取出n个元素的排列。即公式 : A(m,n)
排列算法
- 树形图法
- 程序实现
- 数学实现
1.树形图法如下图所示：
QQ截图20181113113824.jpg
2.程序实现
function show(arr, num) {
var resultNum = 0;
var iNow = 1;
if (num == 1) {
//从m中选1个，就是数组的长度
return arr.length;
}
function change(arr, iNow) {
for (var i = 0; i < arr.length; i++) {
var result = arr.concat(); //为了不产生引用关系
result.splice(i, 1); //依次去掉 A B C D
if (iNow == num) {
resultNum += result.length;
} else {
change(result, iNow + 1); // 下一层 递归
}
}
}
change(arr, iNow + 1);
return resultNum;
}
console.log(show(arr, 2));
// 把排列的结果返回了出来
var arr = ['A', 'B', 'C', 'D'];
function show(arr, num) {
var resultNum = 0;
var resultArr = [];
var iNow = 1;
if (num == 1) {
arr.push(arr.length);
return arr;
}
function change(arr, iNow, str) {
for (var i = 0; i < arr.length; i++) {
var result = arr.concat();
var strClone = str;
strClone += result.splice(i, 1);
if (iNow == num) {
resultNum += result.length;
for (var j = 0; j < result.length; j++) {
resultArr.push(strClone + result[j]);
}
} else {
change(result, iNow + 1, strClone);
}
}
}
change(arr, iNow + 1, '');
resultArr.push(resultNum);
return resultArr; //排列的结果
}
console.log(show(arr, 1));
3.数学实现
A(4,3) = m!/(m-n)!
A(4,3) = 4x3x2x1 / (4-3)
//使用代码实现数学公式
function A(m,n){
return f(m) / f(m-n);
}
function f(num){
if(num<=1){
return 1;
}
return num * f(num-1);
}
console.log(A(3,2)); */
组合
组合概念
从m个不同元素中，任取n(n<=m)个元素不用按照顺序进行排列，叫做从m个不同元素中取出n个元素的组合。即公式 : C(m,n)。
因此，组合和排列的不同之处在于：[A,B]和[B,A] 是两种排列，一种组合
排列算法
- 树形图法
- 程序实现
- 数学实现
1.树形图法如下图所示：
组合树形图.jpg
2.程序实现
var arr = ['A','B','C'];
function show(arr,num){
var resultArr = [];
var iNow = 1;
if(num==1){
arr.push(arr.length);
return arr;
}
function change(arr,iNow,str){
for(var i=0;i<arr.length;i++){
var result = arr.concat();
var strClone = str;
strClone += result.splice(i,1);
if( iNow == num ){
for(var j=0;j<result.length;j++){
resultArr.push(strClone + result[j]);
}
}
else{
change(result,iNow+1,strClone);
}
}
}
change(arr,iNow+1,'');
//console.log( resultArr );
//排序去重
function unique(arr){
for(var i=0;i<arr.length;i++){
arr[i] = arr[i].split('').sort().join('');
}
//console.log(arr);
var result = [];
//去重
var obj = {};
for(var i=0;i<arr.length;i++){
if( !obj[arr[i]] ){
result.push(arr[i]);
obj[arr[i]] = 1;
}
}
return result;
}
resultArr = unique( resultArr );
resultArr.push(resultArr.length);
return resultArr;
}
console.log(show(arr,3));
3.数学实现
A(4,3) = m! / (m-n)!*n!
A(4,3) = 4x3x2x1 / (4-3)x(3x2x1)
//使用代码实现数学公式
function C(m,n){
return f(m) / ( f(m-n) * f(n) );
}
function f(num){
if(num<=1){
return 1;
}
return num * f(num-1);
}
console.log( C(3,3) );
