c# - 使用 Enumerable.Zip 或按位与逻辑查找所有子集

Question

我想找到整数数组的所有子集，所以我的第一个想法是使用大小为 n 位的数字的二进制表示，其中 1 包含而 0 不包含。

例如:

int[] arr = { 3, 4, 5 };

从数字 0 到 7 得到:

0,0,0
0,0,1
0,1,0
0,1,1
1,0,0
...etc

这映射到:

empty
5
4
4,5
3
...etc

为了进行映射，我使用了 Enumerable.Zip。代码是:

public static IEnumerable<byte> ToBinary(this int value, int size)
{
    return ToBinaryStream(value, size).Reverse();
}

private static IEnumerable<byte> ToBinaryStream(int value, int size)
{
    if (value < 0)
        yield break;
    do
    {
        yield return (byte)(value & 1);
        --size;
    }
    while ((value = value >> 1) > 0 || size > 0);
}

int?[] arr = { 1,2,3,4 };

List<int[]> subsets = new List<int[]>();

for (int i = 0; i < (int)Math.Pow(2, (arr.Length)); i++)
{
    var subset = i.ToBinary(arr.Length).Zip(arr, (value, array) => value == 1 ? array : null)
        .Where(a => a != null).Cast<int>().ToArray();
    subsets.Add(subset);
}

看起来效果不错。问题是我如何使用按位与逻辑来做同样的事情？

我想将 1000 映射到数组中的第一个元素，将 1001 映射到第一个和最后一个元素，等等。

Answer 1

检查索引为i 的元素x 是否应该包含在数字num 中:

1. 左移 1 i
2. 按位与 num 的结果
3. 如果结果大于0，包含x

代码如下:

int[] arr = { 1,2,3,4 };

List<int[]> subsets = Enumerable
              .Range(0, (int)Math.Pow(2, (arr.Length)))
              .Select(num => arr.Where((x, i) => ((1 << i) & num) > 0).ToArray())
              .ToList();

它将 num 中的最低位视为数组中的第一个元素，以避免必须颠倒事物。顺便说一句，有趣的想法:)