6

我正在尝试为给定位宽内的一对 1 生成所有可能的组合。

假设位宽为 6，即数字 32。这就是我想要生成的：

000000
000011
000110
001100
001111
011000
011011
011110
110000
110011
110110
111100
111111

如果我有变量：

var a = 1,
    b = 2;
    num = a | b;

并创建一个循环，我会随着width - 1时间的推移循环，在我移动 和a << 1的地方b << 1，我会得到一对的所有组合。在那之后，我几乎被困住了。

有人可以请提供一些帮助。

更新：工作示例
基于 Barmar 的数学方法，这是我设法实现的

var arr = [],
    arrBits = [];

function getCombs(pairs, startIdx) {
    var i, j, val = 0, tmpVal, idx;

    if (startIdx + 2 < pairs) {
        startIdx = arr.length - 1;
        pairs -= 1;
    }

    if (pairs < 2) {
        return;
    }

    for (i = 0; i < pairs-1; i++) {
        idx = startIdx - (i * 2);
        val += arr[idx];

    }

    for (j = 0; j < idx - 1; j++) {
        arrBits.push((val + arr[j]).toString(2));
    }

    getCombs(pairs, startIdx-1);
}

(function initArr(bits) {
    var i, val, pairs, startIdx;

    for (i = 1; i < bits; i++) {
        val = i == 1 ? 3 : val * 2;
        arr.push(val);
        arrBits.push(val.toString(2));
    }

    pairs = Math.floor(bits / 2);
    startIdx = arr.length - 1;

    getCombs(pairs, startIdx);
    console.log(arrBits);

}(9));

JSFiddle 上的工作示例
http://jsfiddle.net/zywc5/

4

5 回答 5

3

恰好有一对 1 的数字是序列 3, 6, 12, 24, 48, ...；他们从 3 开始，每次加倍。

有两对 1 的数是 12+3, 24+3, 24+6, 48+3, 48+6, 48+12, ...；这些是从 12 + 原始序列到 n/4 的上述序列。

三对 1 的数字是 48+12+3, 96+12+3, 96+24+3, 96+24+6, ...

这些中的每一个之间的关系表明使用原始加倍序列的递归算法。我现在没有时间写它，但我认为这应该能让你继续前进。

于 2012-09-05T20:54:51.713 回答
0

如果位宽不是那么大，那么最好在循环中为从 0 到 31 的所有数字创建位表示，并简单地忽略位表示中具有奇数个“1”的那些。

于 2012-09-05T20:44:14.200 回答
0

也许开始以二进制正常计数并将所有 1 替换为 11，如下所示：

n = 5
n = n.toString(2)          //= "101"
n = n.replace(/1/g, "11")  //= "11011"
n = parseInt(n, 2)         //= 27

所以你会得到：

0   -> 0
1   -> 11
10  -> 110
11  -> 1111
100 -> 1100
101 -> 11011
110 -> 11110
111 -> 111111

等等。您必须在左侧数到 31 左右，并在右侧拒绝超过 6 位的数。

于 2012-09-05T20:53:16.873 回答
0

见http://jsfiddle.net/SBH6R/

var len=6,
    arr=[''];
for(var i=0;i<len;i++){
    for(var j=0;j<arr.length;j++){
        var k=j;
        if(getNum1(arr[j])%2===1){
            arr[j]+=1;
        }else{
            if(i<len-1){
                arr.splice(j+1,0,arr[j]+1);
                j++;
            }
            arr[k]+=0;
        }      
    }
}
function getNum1(str){
    var n=0;
    for(var i=str.length-1;i>=0;i--){
        if(str.substr(i,1)==='1'){n++;}
        else{break;}
    }
    return n;
}
document.write(arr.join('<br />'));

或者，也许您会更喜欢http://jsfiddle.net/SBH6R/1/。它更简单，但是您将不得不sort()使用数组：

var len=6,
    arr=[''];
for(var i=0;i<len;i++){
    for(var k=0,l=arr.length;k<l;k++){
        if(getNum1(arr[k])%2===1){
            arr[k]+=1;
        }else{
            if(i<len-1){
                arr.push(arr[k]+1);
            }
            arr[k]+=0;
        }     
    }
}
function getNum1(str){
    var n=0;
    for(var i=str.length-1;i>=0;i--){
        if(str.substr(i,1)==='1'){n++;}
        else{break;}
    }
    return n;
}
document.write(arr.sort().join('<br />'));

如果您想比较性能，请参阅http://jsperf.com/generate-all-combinations-for-pair-of-bits-set-to-1 。似乎最快的代码是 Chrome 上的第一个，而 Firefox 上的第二个。

于 2012-09-05T22:00:47.167 回答
0

You can also do this with bit twiddling. If the lowest two bits are zero, we need to set them, which is equivalent to adding 3. Otherwise, we need to replace the lowest block of ones by its top bit and a 1-bit to the left of it. This can be done as follows, where x is the current combination:

x3 = x + 3;
return (((x ^ x3) - 2) >> 2) + x3;
于 2015-03-15T09:22:56.527 回答