Wygeneruj wszystkie kombinacje dla listy ciągów

Chcę wygenerować listę wszystkich możliwych kombinacji listy ciągów (w rzeczywistości jest to lista obiektów, ale dla uproszczenia użyjemy łańcuchów). Potrzebuję tej listy, aby móc przetestować każdą możliwą kombinację w teście jednostkowym.

Na przykład, jeśli mam listę:

<code>  var allValues = new List<string>() { "A1", "A2", "A3", "B1", "B2", "C1" }
</code>

PotrzebujęList<List<string>> ze wszystkimi kombinacjami, takimi jak:

<code>  A1
  A2
  A3
  B1
  B2
  C1
  A1 A2
  A1 A2 A3
  A1 A2 A3 B1
  A1 A2 A3 B1 B2
  A1 A2 A3 B1 B2 C1
  A1 A3
  A1 A3 B1
  etc...
</code>

Funkcja rekurencyjna jest prawdopodobnie sposobem na uzyskanie wszystkich kombinacji, ale wydaje się trudniejsza niż sobie wyobrażałem.

Jakieś wskazówki?

Dziękuję Ci.

EDYCJA: dwa rozwiązania, z rekursją lub bez:

<code>public class CombinationGenerator<T>
{
    public IEnumerable<List<T>> ProduceWithRecursion(List<T> allValues) 
    {
        for (var i = 0; i < (1 << allValues.Count); i++)
        {
            yield return ConstructSetFromBits(i).Select(n => allValues[n]).ToList();
        }
    }

    private IEnumerable<int> ConstructSetFromBits(int i)
    {
        var n = 0;
        for (; i != 0; i /= 2)
        {
            if ((i & 1) != 0) yield return n;
            n++;
        }
    }

    public List<List<T>> ProduceWithoutRecursion(List<T> allValues)
    {
        var collection = new List<List<T>>();
        for (int counter = 0; counter < (1 << allValues.Count); ++counter)
        {
            List<T> combination = new List<T>();
            for (int i = 0; i < allValues.Count; ++i)
            {
                if ((counter & (1 << i)) == 0)
                    combination.Add(allValues[i]);
            }

            // do something with combination
            collection.Add(combination);
        }
        return collection;
    }
}
</code>

questionAnswers(4)

yourAnswerToTheQuestion