m选n组合算法

01转化法

思路是开一个数组，总长度为m，数组元素的值为1表示被选中，为0则没选中。

• 首先初始化，将数组前n个元素置1，表示第一个组合为前n个数。
• 然后从左到右扫描数组元素值的“10”组合，找到第一个“10”组合后将其变为“01”组合；
• 同时将其左边的所有“1”全部移动到数组的最左端。
• 当第一个“1”移动到数组的m-n的位置，即n个“1”全部移动到最右端时，就得到了最后一个组合。

例如求5选3的组合：

1 1 1 0 0 //1,2,3
 
1 1 0 1 0 //1,2,4
 
1 0 1 1 0 //1,3,4
 
0 1 1 1 0 //2,3,4
 
1 1 0 0 1 //1,2,5
 
1 0 1 0 1 //1,3,5
 
0 1 1 0 1 //2,3,5
 
1 0 0 1 1 //1,4,5
 
0 1 0 1 1 //2,4,5
 
0 0 1 1 1 //3,4,5  

JavaScript实现：

/**
* 获得指定数组的所有组合
*/
function arrayCombine(targetArr) {
   if(!targetArr || !targetArr.length) {
       return [];
   }
   var len = targetArr.length;
   var resultArrs = [];
   // 所有组合
   for(var n = 1; n < len; n++) {
       var flagArrs = getFlagArrs(len, n);
       while(flagArrs.length) {
           var flagArr = flagArrs.shift();
           var combArr = [];
           for(var i = 0; i < len; i++) {
               flagArr[i] && combArr.push(targetArr[i]);
           }
           resultArrs.push(combArr);
       }
   }
   return resultArrs;
};
/**
* 获得从m中取n的所有组合
*/
function getFlagArrs(m, n) {
   if(!n || n < 1) {
       return [];
   }
   var resultArrs = [],
       flagArr = [],
       isEnd = false,
       i, j, leftCnt;
   for (i = 0; i < m; i++) {
       flagArr[i] = i < n ? 1 : 0;
   }
   resultArrs.push(flagArr.concat());
   while (!isEnd) {
       leftCnt = 0;
       for (i = 0; i < m - 1; i++) {
           if (flagArr[i] == 1 && flagArr[i+1] == 0) {
               for(j = 0; j < i; j++) {
                   flagArr[j] = j < leftCnt ? 1 : 0;
               }
               flagArr[i] = 0;
               flagArr[i+1] = 1;
               var aTmp = flagArr.concat();
               resultArrs.push(aTmp);
               if(aTmp.slice(-n).join("").indexOf('0') == -1) {
                   isEnd = true;
               }
               break;
           }
           flagArr[i] == 1 && leftCnt++;
       }
   }
   return resultArrs;
}