[整] JavaScript m选n组合算法

时间:2023-03-08 17:13:39
[整] JavaScript m选n组合算法

01转换法:

思路是开一个数组,其下标表示1到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;
}

应用:[原] 淘宝SKU组合查询算法实现