循环中所有带零的数组组合

Question

给出如下数组

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

我现在想循环输出这些数字与 0 的所有组合。每个数字可以单独出现，也可以与数组中的任何其他数字一起出现（其余应该为 0）。组合时应保持数字的原始位置。

原数组的数字应该保留，只能用零代替。

数组的大小始终保持不变。所以没有额外添加零。所以不可能在增加数组长度的原始数组的数字之间插入零。

并且示例输入有三个 10，例如可以有第一个 10，然后是 0，然后再是 10。

组合的生成顺序没有要求。

我只是想用下面的例子来阐明我的想法。

[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]

这里进行的最佳方式是什么？

Answer 1

该任务实际上转化为生成 15 个二进制数字的二进制数，其中 0 表示“生成 0”，1 表示“从该位置的输入复制数字”。

很明显，有 2¹⁵ 种组合，因为这是使用 15 位可以产生的数字的数量。

因此 JavaScript 中的实现可能是：

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
}

循环中所有带零的数组组合

All array combinations with zero in a loop

java

arrays

algorithm

loops

zero