All possibles combination of zeroes and ones

Question

I have an array, consisting of zeros and ones. For example, arr = [0,0,1,1,1] How can I sort through all possible combinations, in which the number of ones and zeros remains constant (according to the example, the number of zeros is 2 and the number of ones is 3)? In total, there are C(5,3) or C(5,2), where C = n! / ((n-k)! * k!)).

I know how to get all possible combinations of ones and zeros in an array, there are 2 ^ n pieces of them. There is code:

var color = [];
for(var i = 0; i < n;i++) color[i] = 0; 
do{ 
    color[0] += 1;
    for(var i = 0; i < n-1;i++){
        if(color[i] == 2) color[i] = 0, color[i+1] += 1;
            else break;
    }
    if(color[n-1] == 2) break;        
}

while(..);

Welcome to Stack Overflow! StackOverflow expects you to [try to solve your own problem first](http://meta.stackoverflow.com/questions/261592), and we also [don't answer homework questions](https://softwareengineering.meta.stackexchange.com/questions/6166). Please update your question to show what you have already tried in a [minimal, complete, and verifiable example](http://stackoverflow.com/help/mcve). For further information, please see [how to ask good questions](http://stackoverflow.com/help/how-to-ask), and take the [tour of the site](http://stackoverflow.com/tour) :) — Barmar, Jan 06 '18 at 00:15
Do you mean "list" or "iterate" through all combinations of J x 0s and K x 1s, f(J,K) => list of binary numbers? If you want all combinations then it's the count of 0s and 1s that matter. If you want all permutations of k array elements then the count or them being 0s or 1s or 9s or strings does not matter. — Dave S, Jan 06 '18 at 00:17
Possible duplicate of [Permutations in JavaScript?](https://stackoverflow.com/questions/9960908/permutations-in-javascript) — VLAZ, Jan 06 '18 at 00:17
Do you want to keep the array to 5 elements, or find all subset combinations? — Dmitry Pleshkov, Jan 06 '18 at 00:18
Duplicate of [this](https://stackoverflow.com/questions/5752002/find-all-possible-subset-combos-in-an-array)? Is this a homework question? — Dmitry Pleshkov, Jan 06 '18 at 00:20

score 0 · Answer 1 · answered Jan 06 '18 at 02:27

To count bits that are set is a little tricky but there are algorithms out there that will do it. Here is one that I stole from this answer.

function countSetBits(i)
{
    i = i - ((i >> 1) & 0x55555555);
    i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
    return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;
}

If we know how many bits are set, we can infer that the rest of the bits are not set. Then we can loop through all the integers in the appropriate range (the range always starts at 0 and goes up to 2 ^ (total bits) - 1) to find the right numbers, with a function like this:

function generateNumbers(set, clear)
{
    for ( var n = 0; n < Math.pow(2, set + clear); n++)
    {
        if (countSetBits(n) == set)
        output(n);
    }
}

Here is a complete solution:

function countSetBits(i)
{
     i = i - ((i >> 1) & 0x55555555);
     i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
     return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;
}

function output(i)
{
    document.getElementById("Data").innerText += i + "\r\n";
}

function generateNumbers(set, clear)
{
    for ( var n = 0; n < Math.pow(2, set + clear); n++)
    {
        if (countSetBits(n) == set)
        output(n);
    }
}

generateNumbers(2,3);

Output:

Each of the above has 2 bits set to 1 and 3 bits set to 0.

See and run the code on JSFiddle.

All possibles combination of zeroes and ones

1 Answers1