Как получить все подмножества массива?

Легкий понять версию (с описаниями)

я предположил что источник = {1,2,3,4}

public static IEnumerable<IEnumerable<T>> GetSubSets<T>(IEnumerable<T> source)
    {
        var result = new List<IEnumerable<T>>() { new List<T>() }; // empty cluster  added

        for (int i = 0; i < source.Count(); i++)
        {
            var elem = source.Skip(i).Take(1);

            // for elem = 2
            // and currently result = [ [],[1] ]
            var matchUps = result.Select(x => x.Concat(elem));
            //then matchUps => [ [2],[1,2] ]

             result = result.Concat(matchUps).ToList();
            //  matchUps and result concat operation
            // finally result = [ [],[1],[2],[1,2] ]
        }
        return result;
    }

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()));

Вы можете использовать класс 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);
}

Элегантно? Почему бы не Linq it.

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

Вот решение, подобное методу Дэвида Б, но, возможно, более подходящее, если действительно требуется, чтобы вы возвращали наборы с исходным количеством элементов (даже если они пустые):.

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

Если вы передаете список из трех строк, вы получите восемь списков по три элемента в каждом (но некоторые элементы будут нулевыми).

Это небольшое изменение в решении Мехрдада, приведенном выше:

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

или с указателями

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

Вот простое решение в соответствии с вашей концепцией:

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

Я не очень хорошо знаком с C #, но уверен, что в этом есть что-то например:

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

Хорошо, мне сказали, что ответ выше не сработает. Если вы цените элегантность над эффективностью , я бы попробовал рекурсию в моем паршивом псевдокоде:

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