遍历所有可能的组合

Question

我的 objective 是遍历给定数量的 1 和 0 的所有组合。比如说，如果我得到数字 5，那么列出

的足够快的方法是什么

1110100100, 1011000101等（每个不同的 5 个 1 和 5 个 0 的组合）

我试图避免遍历所有可能的排列并检查是否存在 5 个 1，因为 2^n 远大于（n 选择 n/2）。谢谢

更新

可以通过以下方式有效地计算答案（递归 10 深）：

// call combo() to have calculate(b) called with every valid bitset combo exactly once
combo(int index = 0, int numones = 0) {
    static bitset<10> b;
    if( index == 10 ) {
        calculate(b); // can't have too many zeroes or ones, it so must be 5 zero and 5 one
    } else {
        if( 10 - numones < 5 ) { // ignore paths with too many zeroes
            b[index] = 0;
            combo(b, index+1, numones);
        }
        if( numones < 5 ) { // ignore paths with too many ones
            b[index] = 1;
            combo(b, index+1, numones++);
        }
    }
}

（以上代码未测试）

Answer 1

你可以转化问题。如果您修复了 1s（反之亦然），那么这只是您将 0s 放在哪里的问题。对于 5 1s，有 5+1 个 bins，你想在 bins 中放入 5 个元素（0s）。

这可以通过每个箱子的递归和每个箱子的循环来解决（将 0...扩孔元素放入箱子 - 除了最后一个箱子，您必须在其中放置所有剩余元素）。

Answer 2

另一种思考方式是将其作为 string permutation question 的变体 - 只需构建一个长度为 2n 的向量（例如 111000），然后使用相同的字符串置换算法来构建结果。

请注意，朴素算法会打印重复的结果。但是，通过在递归函数中保留一个 bool 数组来保留为特定位设置的值，该算法可以很容易地适应以忽略此类重复项。

遍历所有可能的组合

Iterating through all possible combinations

c++

combinatorics