如何获取数组的所有子集？

Question

给定一个数组: [dog, cat, mouse]

什么是最优雅的创作方式:

[,,]
[,,mouse]
[,cat,]
[,cat,mouse]
[dog,,]
[dog,,mouse]
[dog,cat,]
[dog,cat,mouse]

我需要这个适用于任何大小的数组.

这本质上是一个二进制计数器,其中数组索引代表位.这可能让我使用一些按位运算来计算,但我看不到将其转换为数组索引的好方法.

Answer 1

优雅？为什么不Linq呢.

    public static IEnumerable<IEnumerable<T>> SubSetsOf<T>(IEnumerable<T> source)
    {
        if (!source.Any())
            return Enumerable.Repeat(Enumerable.Empty<T>(), 1);

        var element = source.Take(1);

        var haveNots = SubSetsOf(source.Skip(1));
        var haves = haveNots.Select(set => element.Concat(set));

        return haves.Concat(haveNots);
    }

Answer 2

 string[] source = new string[] { "dog", "cat", "mouse" };
 for (int i = 0; i < Math.Pow(2, source.Length); i++)
 {
     string[] combination = new string[source.Length];
     for (int j = 0; j < source.Length; j++)
     {
         if ((i & (1 << (source.Length - j - 1))) != 0)
         {
             combination[j] = source[j];
         }
    }
    Console.WriteLine("[{0}, {1}, {2}]", combination[0], combination[1], combination[2]);
}

Answer 3

您可以使用BitArray该类轻松访问数字中的位:

string[] animals = { "Dog", "Cat", "Mouse" };
List<string[]> result = new List<string[]>();
int cnt = 1 << animals.Length;
for (int i = 0; i < cnt; i++) {
   string[] item = new string[animals.Length];
   BitArray b = new BitArray(i);
   for (int j = 0; j < item.Length; j++) {
      item[j] = b[j] ? animals[j] : null;
   }
   result.Add(item);
}

Answer 4

static IEnumerable<IEnumerable<T>> GetSubsets<T>(IList<T> set)
{
    var state = new BitArray(set.Count);
    do
        yield return Enumerable.Range(0, state.Count)
                               .Select(i => state[i] ? set[i] : default(T));
    while (Increment(state));
}

static bool Increment(BitArray flags)
{
    int x = flags.Count - 1; 
    while (x >= 0 && flags[x]) flags[x--] = false ;
    if (x >= 0) flags[x] = true;
    return x >= 0;
}

用法:

foreach(var strings in GetSubsets(new[] { "dog", "cat", "mouse" }))
    Console.WriteLine(string.Join(", ", strings.ToArray()));

Answer 5

Guffa 的答案具有我正在搜索的基本功能，但是与

BitArray b = new BitArray(i);

对我不起作用，它给出了一个 ArgumentOutOfRangeException。这是我稍微调整和工作的代码：

string[] array = { "A", "B", "C","D" };
int count = 1 << array.Length; // 2^n

for (int i = 0; i < count; i++)
{
    string[] items = new string[array.Length];
    BitArray b = new BitArray(BitConverter.GetBytes(i));
    for (int bit = 0; bit < array.Length; bit++) {
        items[bit] = b[bit] ? array[bit] : "";
    }
    Console.WriteLine(String.Join("",items));
}