All array combinations with zero in a loop-CodePudding

The following array is given

[10, 10, 10, 50, 50, 100, 100, 100, 500, 500, 500, 1000, 1000, 1000, 5000]

I now want to loop to output all combinations of these numbers with 0. Each number can occur alone or with any other numbers in the array (the rest should be 0). The original position of the numbers should be maintained when they are included in a combination.

The numbers of the original array should remain in place and can only be replaced by a zero or not.

The size of the array always remains the same. So no zeros are added additionally. So it is not possible to insert zeros between the numbers of the original array increasing the length of the array.

And as the example input has three 10s, it is for example possible to have the first 10, then 0, and then 10 again.

There is no requirement for the order in which the combinations are produced.

I just want to clarify my idea with the following example.

[10,  0,  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[10, 10,  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0,  10,  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[10, 10, 10, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0,  10, 10, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[10, 10, 10, 50, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0,   0,  0, 50, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0,   0, 10, 50, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0,   10, 10, 50, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[10, 10, 10, 50, 50, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 50, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 50, 50, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 10, 50, 50, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 10, 10, 50, 50, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[10, 10, 10, 50, 50, 100, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 10, 10, 50, 50, 100, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 10, 50, 50, 100, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 50, 50, 100, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

What would be the best way to proceed here?

CodePudding user response：

The task really translates to producing binary numbers of 15 binary digits, where a 0 means "produce a 0" and a 1 means "copy the number from the input at this position".

It is then clear that there are 2¹⁵ combinations as that is the number of numbers you can produce using 15 bits.

So an implementation in JavaScript could be:

let input = [10, 10, 10, 50, 50, 100, 100, 100, 500, 500, 500, 1000, 1000, 1000, 5000];

let quit = 20; // For demo purpose, let's stop after 20 outputs...
let count = Math.pow(2, 15); // Total number of combinations
for (let i = 0; i < count; i  ) { // For each combination
    let combi = []; // Create new empty array
    for (let bit = 0, bits = i; bit < 15; bit  , bits >>= 1) {
        // Depending on bit, either append 0 or the input to the array
        combi.push(bits & 1 ? input[bit] : 0); 
    }
    console.log(...combi); // Output all values in the array
    if (quit-- < 0) break; // For this demo only
}