c# - 迭代获取特定集合的所有子集

Question

我知道迭代解决方案:

给定一组n个元素

保存一个 int v = 2^n 并生成所有二进制数直到这个 v。

但是如果 n > 32 呢？

我知道它已经是 2^32 个子集，但是 - 绕过 32 个元素限制的方法是什么？

Answer 1

1. 如果您对 64 项限制感到满意，您可以简单地使用 long。

2. int/long 的数组/ArrayList。有一个类似next 的函数:

   bool next(uint[] arr)
     for (int i = 0; i < arr.length; i++)
       if (arr[i] == 2^n-1) // 11111 -> 00000
         arr[i] = 0
       else
         arr[i]++
         return true
     return false // reached the end -> there is no next
   

3. BitArray .与上述相比，可能不是一个非常有效的选择。

   您可以使用 next 函数将最低有效位 0 设置为 1，并将所有剩余位设置为 0。例如:

   10010 -> 10011
   10011 -> 10100
   

注意 - 这可能需要很长时间，因为子集太多了，但这不是问题所在。