Gere todas as combinações para uma lista de strings

Eu quero gerar uma lista de todas as combinações possíveis de uma lista de seqüências de caracteres (na verdade, é uma lista de objetos, mas para simplificar, vamos usar seqüências de caracteres). Eu preciso dessa lista para poder testar todas as combinações possíveis em um teste de unidade.

Por exemplo, se eu tiver uma lista de:

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

eu preciso deList<List<string>> com todas as combinações como:

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

Uma função recursiva é provavelmente a maneira de fazer isso para obter todas as combinações, mas parece mais difícil do que eu imaginava.

Quaisquer ponteiros?

Obrigado.

EDIT: duas soluções, com ou sem recursividade:

<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