c++ - 二进制数的所有组合，其中仅某些位可以更改

Question

我想知道是否有一种算法可以生成二进制数的所有可能组合，其中只有某些位置的位可以更改，例如，我们具有以下位流，但是只有位置x中标记的位可以更改(此示例具有可以更改以形成不同组合的8个位置，总计2 ^ 8):x00x0000x000000x00x00x000x000x一种解决方案是首先将数字视为8位数字，然后只计算xxxxxxxx的所有组合。
但是，这不能完全满足我的需求，因为稍后我想在线性移位寄存器(LFSR)中使用数字，目前，我正在寻找利用std::bitset的答案。

Answer 1

因此，已经有一个答案。但是只是转储了代码，没有任何解释。不好。不确定，为什么接受。无论如何...
我想用另一种方法添加答案，并解释步骤。
基本上，如果要具有二进制数的所有组合，则可以简单地“计数”或“递增1”。 3位值的示例。这将是十进制的0、1、2、3、4、5、6、7和二进制000、001、010、011、100、101、110、111。您会发现这很简单。
如果我们回想起上学 bool(boolean) bool(boolean) 代数和一些自动机理论的上学时间，那么我们就会沉迷于该计数操作是如何在低水平完成的。我们总是翻转最低有效位，并且，如果从1过渡到0，那么我们基本上发生了溢出，还必须翻转下一位。这就是二进制加法器的原理。我们想在我们的例子中总是加1。因此，将1加0，结果为1，则没有溢出。但是将1加1，结果为0，那么我们有一个过高的情况，必须在下一位加1。这将有效地翻转下一位，依此类推。
这种方法的优点是，我们不必总是对所有位进行操作。因此，复杂度不是O(n)，而是O(log n)。
附加优点:它非常适合您使用std::bitset的请求。
第三个优点，也许不是那么明显:您可以将计算下一个组合的任务与程序的其余部分分离。无需在这种功能中集成您的实际任务代码。这也是为什么std::next_permutation这样实现的原因。
并且，上面描述的算法适用于所有值，无需排序或任何必需的操作。
那部分是您要的算法。

下一部分是针对您的请求，仅某些位可以更改。当然，我们需要指定这些位。而且由于您正在使用std::bitset屏蔽，因此这里没有解决方案。更好的方法是使用索引。含义，给出允许更改的位的位位置。
然后，我们可以使用上述算法，仅需一个附加的间接寻址。因此，我们不使用bits[pos]，而是bits[index[pos]]。
使用初始化列表可以轻松地将索引存储在std::vector中。我们还可以从字符串或其他任何东西派生索引 vector 。我以std::string为例。

以上所有内容将导致一些简短的代码，只有几行，并且易于理解。我还添加了一些使用此功能的驱动程序代码。
请参阅:

#include <iostream>
#include <vector>
#include <string>
#include <bitset>
#include <algorithm>
#include <cassert>

constexpr size_t BitSetSize = 32U;

void nextCombination(std::bitset<BitSetSize>& bits, const std::vector<size_t>& indices) {

    for (size_t i{}; i < indices.size(); ++i) {

        // Get the current index, and check, if it is valid
        if (const size_t pos = indices[i]; pos < BitSetSize) {

            // Flip bit at lowest positions
            bits[pos].flip();

            // If there is no transition of the just flipped bit, then stop
            // If there is a transition from high to low, then we need to flip the next bit
            if (bits.test(pos))
                break;
        }
    }
}

// Some driver code
int main() {
    // Use any kind of mechanism to indicate which index should be changed or not
    std::string mask{ "x00x0000x000000x00x00x000x000x" };

    // Here, we will store the indices
    std::vector<size_t> index{};
    // Populated the indices vector from the string
    std::for_each(mask.crbegin(), mask.crend(), [&, i = 0U](const char c) mutable {if ('x' == c) index.push_back(i); ++i; });

    // The bitset, for which we want to calculate the combinations
    std::bitset<BitSetSize> bits(0);

    // Play around
    for (size_t combination{}; combination < (1 << (index.size())); ++combination) {

        // This is the do something
        std::cout << bits.to_string() << '\n';

        // calculate the next permutation
        nextCombination(bits, index);
    }
    return 0;
}

该软件已使用C++ 17通过MSVC 19社区版进行编译
如果您还有其他问题或需要更多说明，那么我很乐意回答