Quiero generar una lista de todas las combinaciones posibles de una lista de cadenas (en realidad es una lista de objetos, pero por simplicidad usaremos cadenas). Necesito esta lista para poder probar cada combinación posible en una prueba unitaria.

Así por ejemplo si tengo una lista de:

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

necesito unList<List<string>> con todas las combinaciones 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>

Una función recursiva es probablemente la forma de hacerlo para obtener todas las combinaciones, pero parece más difícil de lo que imaginaba.

Cualquier punteros?

Gracias.

EDITAR: dos soluciones, con o sin recursión:

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