mediante LINQ para iterar combinaciones

Question

Duplicar posibles:
Generating all Possible Combinations
Is there a good LINQ way to do a cartesian product?
How to generate combination of N elements with limited supply of 2 each without explicit nested loops

tengo una lista de listas, y quiero repetir todas las posibles combinaciones en las que me elige un elemento de cada lista interna. Esto es bastante sencillo si sé en tiempo de compilación cuántas listas hay, pero ¿cómo puedo hacerlo cuando no sé saber de antemano cuántas listas habrá?

Si tengo tres listas (y si sé, en tiempo de compilación, que habrá exactamente tres listas), y quiero todas las combinaciones de elegir un solo elemento de cada una de las tres listas, puedo tan fácilmente con una consulta LINQ:

var list1 = new[] { 1, 2 }; 
var list2 = new[] { 3, 4 }; 
var list3 = new[] { 5, 6 }; 
var combinations = from item1 in list1 
        from item2 in list2 
        from item3 in list3 
        select new[] { item1, item2, item3 }; 
// Results: 
// {1, 3, 5} 
// {1, 3, 6} 
// {1, 4, 5} 
// {1, 4, 6} 
// {2, 3, 5} 
// {2, 3, 6} 
// {2, 4, 5} 
// {2, 4, 6} 

Pero ¿cómo puedo hacer lo mismo cuando no sé en tiempo de compilación cuántas listas habrá?

var lists = new[] { 
    new[] { 1, 2 }, 
    new[] { 3, 4 }, 
    new[] { 5, 6 } }; 
var combinations = ???; 

// This particular example happens to be the same inputs as above, so it 
// has the same expected outputs. But there could be two lists instead, 
// or four, so the three hard-coded "from" clauses won't work. 

Parece que esto en realidad debería ser factible en LINQ - SelectMany ya lo hace el equivalente a dos foreach anidados, por lo que todo lo que necesita hacer es hacer un montón de llamadas SelectMany y luego combinar todos los resultados con otro SelectMany. O algo. Pero cuando comienza a obtener meta así, mi cerebro queda atado en nudos. No puedo entender cómo juntar las piezas. Ni siquiera puedo descifrar cuáles serían los argumentos de tipo genérico para la llamada externa de SelectMany.

¿Cómo puedo iterar esas listas de listas y devolver todas las combinaciones, sin saber en tiempo de compilación cuántas listas habrá?

(Nota: en todos los lugares donde utilicé las matrices anteriores, estaría bien si usara IEnumerable<T>. Las matrices son más fáciles de escribir en el código de muestra, pero estoy esperando que la salida sea más bien en el formato IEnumerable<IEnumerable<int>> que el int[][] que muestro en mi salida de muestra anterior.)

Answer 1

No usa SelectMany para combinar las llamadas SelectMany; Usas Agregado. cortesía Código de Eric Lippert (respondiendo sobre una cuestión que es mucho más específico que éste, pero dando una respuesta general que se ajuste a esta pregunta también):

static IEnumerable<IEnumerable<T>> CartesianProduct<T>(
    this IEnumerable<IEnumerable<T>> sequences) 
{ 
    IEnumerable<IEnumerable<T>> emptyProduct = new[] { Enumerable.Empty<T>() }; 
    return sequences.Aggregate(
     emptyProduct, 
     (accumulator, sequence) => 
      from accseq in accumulator 
      from item in sequence 
      select accseq.Concat(new[] {item}) :       
     ); 
} 

Al igual que con todas las respuestas de Eric, que incluye un detailed discussion que establece exactamente cómo y por qué funciona esto, en términos del código equivalente que no es LINQ.