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

How to get all subsets of an array?

提问by Andrew Bullock

Given an array: [dog, cat, mouse]

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

what is the most elegant way to create:

什么是最优雅的创建方式：

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

I need this to work for any sized array.

我需要它适用于任何大小的数组。

This is essentially a binary counter, where array indices represent bits. This presumably lets me use some bitwise operation to count, but I can't see a nice way of translating this to array indices though.

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

采纳答案by Michael

 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]);
}

回答by Mehrdad Afshari

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;
}

Usage:

用法：

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

回答by ilya n.

I'm not very familiar with C# but I'm sure there's something like:

我对 C# 不是很熟悉，但我确定有类似的东西：

// input: Array A
foreach S in AllSubsetsOf1ToN(A.Length): 
    print (S.toArray().map(lambda x |> A[x]));

---

---

Ok, I've been told the answer above won't work. If you value elegance over efficiency, I would try recursion, in my crappy pseudocode:

好的，有人告诉我上面的答案不起作用。如果你重视优雅而不是效率，我会在我蹩脚的伪代码中尝试递归：

Array_Of_Sets subsets(Array a) 
{
    if (a.length == 0) 
         return [new Set();] // emptyset
    return subsets(a[1:]) + subsets(a[1:]) . map(lambda x |> x.add a[0]) 
}

回答by mqp

Here's an easy-to-follow solution along the lines of your conception:

这是一个易于遵循的解决方案，符合您的概念：

private static void Test()
{
    string[] test = new string[3] { "dog", "cat", "mouse" };

    foreach (var x in Subsets(test))
        Console.WriteLine("[{0}]", string.Join(",", x));
}

public static IEnumerable<T[]> Subsets<T>(T[] source)
{
    int max = 1 << source.Length;
    for (int i = 0; i < max; i++)
    {
        T[] combination = new T[source.Length];

        for (int j = 0; j < source.Length; j++)
        {
            int tailIndex = source.Length - j - 1;
            combination[tailIndex] =
                ((i & (1 << j)) != 0) ? source[tailIndex] : default(T);
        }

        yield return combination;
    }
}

回答by Guffa

You can use the BitArrayclass to easily access the bits in a number:

您可以使用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);
}

回答by ilya n.

This is a small change to Mehrdad's solution above:

这是对上述 Mehrdad 解决方案的一个小改动：

static IEnumerable<T[]> GetSubsets<T>(T[] set) {
    bool[] state = new bool[set.Length+1];
    for (int x; !state[set.Length]; state[x] = true ) {
        yield return Enumerable.Range(0, state.Length)
                               .Where(i => state[i])
                               .Select(i => set[i])
                               .ToArray();
        for (x = 0; state[x]; state[x++] = false);
    }
}

or with pointers

或用指针

static IEnumerable<T[]> GetSubsets<T>(T[] set) {
    bool[] state = new bool[set.Length+1];
    for (bool *x; !state[set.Length]; *x = true ) {
        yield return Enumerable.Range(0, state.Length)
                               .Where(i => state[i])
                               .Select(i => set[i])
                               .ToArray();
        for (x = state; *x; *x++ = false);
    }
}

回答by Amy B

Elegant? Why not Linq it.

优雅的？为什么不是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);
    }

回答by Ryan Lundy

Here's a solution similar to David B's method, but perhaps more suitable if it's really a requirement that you get back sets with the original number of elements (even if empty):.

这是一个类似于 David B 的方法的解决方案，但如果确实需要您返回具有原始元素数量的集合（即使为空），则可能更合适：。

static public List<List<T>> GetSubsets<T>(IEnumerable<T> originalList)
{
    if (originalList.Count() == 0)
        return new List<List<T>>() { new List<T>() };

    var setsFound = new List<List<T>>();
    foreach (var list in GetSubsets(originalList.Skip(1)))
    {                
        setsFound.Add(originalList.Take(1).Concat(list).ToList());
        setsFound.Add(new List<T>() { default(T) }.Concat(list).ToList());
    }
    return setsFound;
}

If you pass in a list of three strings, you'll get back eight lists with three elements each (but some elements will be null).

如果您传入一个包含三个字符串的列表，您将返回八个列表，每个列表包含三个元素（但有些元素将为空）。

回答by Jeankes

Guffa's answer had the basic functionality that I was searching, however the line with

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

BitArray b = new BitArray(i);

did not work for me, it gave an ArgumentOutOfRangeException. Here's my slightly adjusted and working code:

对我不起作用，它给出了一个 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));
}

回答by Theodor Zoulias

Here is a variant of mqp's answer, that uses as state a BigIntegerinstead of an int, to avoid overflow for collections containing more than 30 elements:

这是 mqp's answer 的一个变体，它使用状态 aBigInteger而不是 an int，以避免包含超过 30 个元素的集合溢出：

using System.Numerics;

public static IEnumerable<IEnumerable<T>> GetSubsets<T>(IList<T> source)
{
    BigInteger combinations = BigInteger.One << source.Count;
    for (BigInteger i = 0; i < combinations; i++)
    {
        yield return Enumerable.Range(0, source.Count)
            .Select(j => (i & (BigInteger.One << j)) != 0 ? source[j] : default);
    }
}