c# - 遍历 BitArray 中所有可能的值组合

Question

我正在尝试解决一个更大的问题。作为其中的一部分，我创建了一个 BitArray 来表示一系列按顺序做出的二元决策。我知道所有有效的决策系列都会有一半的决策是正确的，一半是错误的，但我不知道顺序:

 ttttffff
[||||||||]

或者:

 tftftftf
[||||||||]

或者:

 ttffttff
[||||||||]

或任何其他组合，其中所有位的一半为真，一半为假。

我的 BitArray 比这长很多，我需要遍历每组可能的决定(每个可能的半真半假组合)，进一步检查它们的有效性。然而，我正在努力从概念上弄清楚如何用循环来做到这一点。看起来应该很简单，但我的大脑让我失望了。

编辑:因为 BitArray 不是很大，所以我使用了 usr 的建议并实现了一个位移循环。根据一些评论和答案，我用关键字“排列”重新搜索问题并找到 this非常相似的 Stack Overflow 问题。

Answer 1

我会使用递归算法来执行此操作。每个级别设置下一位。您跟踪已经确定了多少个零和一个。如果其中一个计数器超过 N / 2您中止分支并回溯。这应该会提供很好的性能，因为它会倾向于快速切断不可行的分支。例如，设置后 tttt只有f选择是可行的。

一个更简单、性能较差的版本是使用 for 循环遍历所有可能的 N 位整数，并丢弃不满足条件的整数。对于最多 63 位，这很容易实现。只需要来自 0 的 for 循环至 1 << 63 .显然，对于高比特数，这太慢了。

您正在寻找 N / 2 的所有排列零和 N / 2那些。有生成这些的算法。如果你能找到一个实现的，这应该会提供最好的性能。我相信这些算法使用巧妙的数学技巧来仅访问可行的组合。