1

整数の配列のすべてのサブセットを見つけたかったので、最初に考えたのは、サイズnビットの数値の2進表現を使用することでした。ここで、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);
}

うまく機能しているようです。問題は、ビット単位のANDロジックを使用して同じことを行うにはどうすればよいですか？

1000を配列の最初の要素にマップし、1001を最初と最後の要素にマップします。

4

1 に答える 1

1

xインデックスを持つ要素をi数値に含める必要があるかどうかを確認するにはnum：

  1. 1を左にシフトi
  2. ビットごとのAND結果と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 に答える