循环BitArray中所有可能的值组合

本文关键字：组合 有可能 BitArray 循环 | 更新日期: 2023-09-27 18:05:19

我想解决一个更大的问题。作为其中的一部分，我创建了一个BitArray来表示一系列依次进行的二进制决策。我知道所有有效的决策序列都有一半为真，一半为假，但我不知道顺序:

 ttttffff
[||||||||]

或:

 tftftftf
[||||||||]

或:

 ttffttff
[||||||||]

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

我的BitArray比这长得多，我需要浏览每一组可能的决定(每种可能的半真半假的组合)，进一步检查它们的有效性。然而，我正在努力从概念上解决如何使用循环来做到这一点。这看起来应该很简单，但是我的脑子出问题了。

编辑:因为BitArray不是很大，我使用了usr的建议并实现了位移循环。基于一些评论和答案，我用关键词"排列"重新搜索了这个问题，发现了这个非常相似的Stack Overflow问题。

循环BitArray中所有可能的值组合

我将使用递归算法来完成此操作。每个关卡设置下一个位。你记录下已经决定了多少个0和1。如果其中一个计数器高于N / 2，你中止分支并回溯。这将提供相当好的性能，因为它将倾向于快速切断不可行的分支。例如，设置tttt后，只有f选项是可行的。

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

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

如果您同意使用整数中的位而不是BitArray，这是一种通用的解决方案，可以使用一些固定数量的位集生成所有模式。

从最低有效值开始，即数字右侧的所有有效值，您可以计算为low = ~(-1 << k)(不适用于k=32，但在这种情况下这不是问题)。

然后采用Gosper的Hack(也显示在这个答案中)，这是一种生成下一个具有相同位数的最高整数的方法，并继续应用它，直到达到最高有效值，在本例中为low << k。

这将导致重复项，但如果您愿意，可以在添加到列表之前检查是否有重复项。

  static void Main(string[] args)
  {
     // Set your bits here:
     bool[] bits = { true, true, false };
     BitArray original_bits = new BitArray(bits);
     permuteBits(original_bits, 0, original_bits.Length - 1);
     foreach (BitArray ba in permutations)
     {
        // You can check Validity Here
        foreach (bool i in ba)
        {
           Console.Write(Convert.ToInt32(i));
        }
        Console.WriteLine();
     }
  }
  static List<BitArray> permutations = new List<BitArray>();
  static void permuteBits(BitArray bits, int minIndex, int maxIndex)
  {
     int current_index;
     if (minIndex == maxIndex)
     {
        permutations.Add(new BitArray(bits));
     }
     else
     {
        for (current_index = minIndex; current_index <= maxIndex; current_index++)
        {
           swap(bits, minIndex, current_index);
           permuteBits(bits, minIndex + 1, maxIndex);
           swap(bits, minIndex, current_index);
        }
     }
  }
  private static void swap(BitArray bits, int i, int j)
  {
     bool temp = bits[i];
     bits[i] = bits[j];
     bits[j] = temp;
  }

如果您想清除具有重复条目的字符串的finding all the permutation的概念(i。在zeros and ones)，您可以阅读这篇文章

他们用递归法解决了这个问题，解释也很好。

相关文章：