排列

排列概念

从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) );