1

我想找到整数数组的所有子集，所以我的第一个想法是使用大小为 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 映射到第一个和最后一个等。

4

1 回答 1

1

要检查一个x带有索引的元素i是否应该包含在一个数字中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视为数组中的第一个元素，以避免反转。顺便说一句有趣的想法:)

于 2012-12-10T02:13:35.800 回答