粗浅的排列组合算法之 JavaScript 实现

Friday, 14. December 2007, 08:28:29

东拼西凑加修改，做了几个函数，用于实现排列组合。函数如下：

/**
 * 克隆数组
 */
Array.prototype.clone = function () {
    return this.concat();
};

/**
 * 按指定的顺序数组重新排列
 */
Array.prototype.reOrder = function ( aOrder ) {
    var aClone = this.clone();
    for (var i=0; i < aOrder.length; i++) {
        this[aOrder[i]] = aClone[i];
    }
    return this;
};

/**
 * 取得 0 到 iLen 的所有排列顺序
 */
function getOrders( iLen ) {
    var aResult = [];
    var aNum = [];
    var aNumFlag = [];
    var i, j;
    for(i = 0; i < iLen; i++) {
        aNum[i] = i,
        aNumFlag[i] = 1;
    }
    
    for(;;){
        aResult.push(aNum.clone());
        aNumFlag[aNum[iLen-1]] = 0;
        for(i = iLen - 2; i>=0; i--){
            aNumFlag[aNum[i]] = 0;
            if(aNum[i] < aNum[i+1]) {
                break;
            }
        }
        if( i < 0) {
            break;
        }

        for(j = aNum[i] + 1; j < iLen; j++){
            if(!aNumFlag[j]) {
                break;
            }
        }

        aNumFlag[j] = 1;
        aNum[i] = j;
        for(j=0, i++; i < iLen; j++) {
            if(!aNumFlag[j]) {
                aNum[i++] = j;
                aNumFlag[j] = 1;
            }
        }
    }
    return aResult;
}

/**
 * 生成数组的全排列
 * 方法: 先生成数组长度以下的所有顺序, 然后根据顺序数组重排原数组
 */
function arrayInAllOrder( aData ) { 
    var aResult = []; 
    var aOrders = getOrders(aData.length);
    var aOrder = aOrders.shift();
    while(aOrder) {
        aResult.push(aData.clone().reOrder(aOrder));
        aOrder = aOrders.shift();
    }
    return aResult;
}

/**
 * 得到从 m 元素中取 n 元素的所有组合
 * 结果为[0,1...]形式的数组, 1表示选中，0表示不选
 */
function getCombFlags(m, n) {
    if(n == null || n < 1) {
        return [];
    }

    var aResult = [];
    var aFlag = [];
    for (i=0; i<m; i++) {
        aFlag[i] = (i < n) ? 1 : 0;
    }

    aResult.push(aFlag.clone());
    var bNext = true;
    while (bNext) {
        var iCnt1 = 0;
        for (var i = 0; i < m - 1; i++) {
            if (aFlag[i] == 1) {
                if(aFlag[i+1] == 0) {
                    for(j = 0; j < i; j++) {
                        aFlag[j] =  (j < iCnt1) ? 1 : 0;
                    }
                    aFlag[i] = 0;
                    aFlag[i+1] = 1;
                    var aTmp = aFlag.clone();
                    aResult.push(aTmp);
                    if(aTmp.slice(-n).join("").indexOf('0') == -1) {
                        bNext = false;
                    }
                    break;
                }
                iCnt1++;
            }
        }
    }
    return aResult;
} 

/**
 * 从数组中生成指定长度的组合
 * 方法: 先生成[0,1...]形式的数组, 然后根据0,1从原数组取元素，得到组合数组
 */
function combInArray( aData, n) {
    var aResult = [];
    if(n > aData.length) {
        return aResult;
    }
    
    var aaFlags = getCombFlags(aData.length, n);
    var aFlag = aaFlags.shift();
    while(aFlag) {
        var aComb = [];
        for(var i = 0; i < aData.length; i++) {
            if(aFlag[i]) {
                aComb.push(aData[i]);
            }
        }
        aResult.push(aComb);
        aFlag = aaFlags.shift();
    }
    
    
    return aResult;
}

测试一

document.write("3以下的所有排列顺序:
"); 
var aOut = getOrders(3);
for(var i=0;i<aOut.length;i++) {
    document.write(aOut[i].join(","),"
"); 
}

测试二

var aData = ['a','b','c','d'];
document.write("
数组[" + aData.join(" ") + "]的排列:
"); 
var aOut = arrayInAllOrder(aData);
for(var i=0;i<aOut.length;i++) {
    document.write(aOut[i].join(" ") + "
"); 
}

测试三

document.write("
5取3标志位数组:
"); 
var aOut = getCombFlags(5, 3);
for(var i=0;i<aOut.length;i++) {
    document.write(aOut[i].join(" ") + "
"); 
}

测试四

var aData = ['a','b','c','d','e'];
document.write("
数组[" + aData.join(" ") + "]的3元素组合:
"); 
var aOut = combInArray(aData, 3);
for(var i=0;i<aOut.length;i++) {
    document.write(aOut[i].join(" ") + "
"); 
}

用于测试的HTML文件
plzhfunc.html

【补充】
可重复组合算法的JavaScript实现
最简单的全排列算法

发现一个好东西: JSONER可重复组合算法的JavaScript实现