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組合查詢算法實作