Generar todas Las Combinaciones Posibles

Seguro. Es un poco complicado hacer esto con LINQ, pero ciertamente es posible usar solo los operadores de consulta estándar.

ACTUALIZACIÓN: Este es el tema de mi blog el lunes 28 de junio de 2010; gracias por la gran pregunta. Además, un comentarista en mi blog señaló que hay una consulta aún más elegante que la que di. Actualizaré el código para usarlo.

La parte difícil es hacer el producto cartesiano de arbitrariamente muchas secuencias. "Zipping" en las letras es trivial comparado con eso. Usted debe estudiar esto para asegurarse de que usted entiende cómo funciona. Cada parte es bastante simple, pero la forma en que se combinan juntos toma un poco de acostumbrarse a:

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

Para explicar cómo funciona esto, primero entienda lo que está haciendo la operación "acumular". La operación de acumulación más simple es "añadir todo en esta secuencia juntos". La forma de hacerlo es empezar con cero. Para cada elemento de la secuencia, el valor actual del acumulador es igual a la suma del elemento y el valor anterior del acumulador. Estamos haciendo lo mismo, excepto que en lugar de acumular la suma basada en la suma hasta ahora y el elemento actual, estamos acumulando el producto cartesiano a medida que avanzamos.

La forma en que vamos a hacerlo es aprovechar el hecho de que ya tenemos un operador en LINQ que calcula el producto cartesiano de dos cosas: {[26]]}

from x in xs
from y in ys
do something with each possible (x, y)

Tomando repetidamente el producto cartesiano del acumulador con el siguiente elemento en la secuencia de entrada y haciendo un poco de pegar juntos de los resultados, podemos generar el producto cartesiano a medida que avanzamos.

Así que piensa en el valor del acumulador. Para fines ilustrativos voy a mostrar el valor del acumulador como los resultados de los operadores de secuencia que contiene. Eso no es lo que el acumulador en realidad contiene. Lo que el acumulador realmente contiene son los operadores que producen estos resultados. Entero la operación aquí solo construye un árbol masivo de operadores de secuencia, cuyo resultado es el producto cartesiano. Pero el producto cartesiano final en sí no se calcula realmente hasta que se ejecuta la consulta. Para fines ilustrativos, mostraré cuáles son los resultados en cada etapa del camino, pero recuerde, esto en realidad contiene los operadores que producen esos resultados.

Supongamos que estamos tomando el producto cartesiano de la secuencia de secuencias {{1, 2}, {3, 4}, {5, 6}}. El acumulador comienza como una secuencia que contiene una secuencia vacía: { { } }

En la primera acumulación, el acumulador es { { } } y el elemento es {1, 2}. Hacemos esto:

from accseq in accumulator
from item in sequence 
select accseq.Concat(new[] {item})

Por Lo que estamos tomando el producto Cartesiano de { { } } con {1, 2}, y para cada par, podemos concatenar: Tenemos el par ({ }, 1), así que concatenar { } y {1} para obtener {1}. Tenemos el par ({ }, 2}), así que concatenar { } y {2} para obtener {2}. Por lo tanto tenemos {{1}, {2}} como el resultado.

Así que en la segunda acumulación, el acumulador es {{1}, {2}} y el elemento es {3, 4}. De nuevo, calculamos el producto cartesiano de estas dos secuencias para obtener:

 {({1}, 3), ({1}, 4), ({2}, 3), ({2}, 4)}

Y luego de esos elementos, concatenar el segundo en el primero. Así que el resultado es la secuencia {{1, 3}, {1, 4}, {2, 3}, {2, 4}}, que es lo que queremos.

Ahora acumulamos de nuevo. Tomamos el producto Cartesiano del acumulador con {5, 6} para obtener

 {({ 1, 3}, 5), ({1, 3}, 6), ({1, 4}, 5), ...

Y luego concatenar el segundo elemento en el primero para obtener:

{{1, 3, 5}, {1, 3, 6}, {1, 4, 5}, {1, 4, 6} ... }

Y hemos terminado. Hemos acumulado el producto cartesiano.

Ahora que tenemos una función de utilidad que puede tomar el producto cartesiano de arbitrariamente muchas secuencias, el resto es fácil en comparación:

var arr1 = new[] {"a", "b", "c"};
var arr2 = new[] { 3, 2, 4 };
var result = from cpLine in CartesianProduct(
                 from count in arr2 select Enumerable.Range(1, count)) 
             select cpLine.Zip(arr1, (x1, x2) => x2 + x1);

Y ahora tenemos una secuencia de secuencias de cadenas, una secuencia de cadenas por línea:{[26]]}

foreach (var line in result)
{
    foreach (var s in line)
        Console.Write(s);
    Console.WriteLine();
}

Fácil peasy!

Solución alternativa:

Paso uno: lea mi serie de artículos sobre cómo generar todas las cadenas que coinciden con una gramática sensible al contexto:

Http://blogs.msdn.com/b/ericlippert/archive/tags/grammars /

Paso dos: defina una gramática que genere el idioma que desea. Por ejemplo, podría definir la gramática:

S: a A b B c C
A: 1 | 2 | 3
B: 1 | 2
C: 1 | 2 | 3 | 4

Claramente puede generar fácilmente esa cadena de definición gramatical a partir de sus dos matrices. Luego alimente eso en el código que genera todas las cadenas en una gramática dada, y ya está; obtendrá todas las posibilidades. (No necesariamente en el orden en que los quieres, eso sí.)

Para la comparación, aquí hay una manera de hacerlo con Python

from itertools import product
X=["a", "b", "c"]
Y=[3, 4, 2]
terms = (["%s%s"%(x,i+1) for i in range(y)] for x,y in zip(X,Y))
for item in product(*terms):
    print " ".join(item)

Fon otra solución no basada en linq se puede utilizar:

public class CartesianProduct<T>
    {
        int[] lengths;
        T[][] arrays;
        public CartesianProduct(params  T[][] arrays)
        {
            lengths = arrays.Select(k => k.Length).ToArray();
            if (lengths.Any(l => l == 0))
                throw new ArgumentException("Zero lenght array unhandled.");
            this.arrays = arrays;
        }
        public IEnumerable<T[]> Get()
        {
            int[] walk = new int[arrays.Length];
            int x = 0;
            yield return walk.Select(k => arrays[x++][k]).ToArray();
            while (Next(walk))
            {
                x = 0;
                yield return walk.Select(k => arrays[x++][k]).ToArray();
            }

        }
        private bool Next(int[] walk)
        {
            int whoIncrement = 0;
            while (whoIncrement < walk.Length)
            {
                if (walk[whoIncrement] < lengths[whoIncrement] - 1)
                {
                    walk[whoIncrement]++;
                    return true;
                }
                else
                {
                    walk[whoIncrement] = 0;
                    whoIncrement++;
                }
            }
            return false;
        }
    }

Usted puede encontrar un ejemplo en cómo usarlo aquí.

No estoy dispuesto a darte el código fuente completo. Así que esta es la idea detrás.

Puede generar los elementos de la siguiente manera:

Asumo A=(a1, a2, ..., an) y B=(b1, b2, ..., bn) (así que A y B cada uno tiene elementos n).

¡Entonces hazlo recursivamente! Escribe un método que tome un A y un B y haga lo tuyo:

Si A y B cada uno contiene un solo elemento (llamado an resp. bn), simplemente iterar de 1 a bn y concatenar an a su variable iterante.

Si A y B cada uno contiene más de un elemento, tome los primeros elementos (a1 resp b1), itere de 1 a bn y haga para cada paso de iteración:

• llama al método recursivamente con los subcampos de A y B comenzando en el segundo elemento, es decir, A'=(a2, a3, ..., an) resp B'=(b2, b3, ..., bn). Para cada elemento generado por la llamada recursiva, concatenar a1, la variable iterante y el elemento generado desde la llamada recursiva llamada.

Aquí puedes encontrar un ejemplo analouge de cómo generar cosas en C#, solo tienes que adaptarlo a tus necesidades.

Si lo estoy haciendo bien, estás buscando algo como Producto cartesiano. Si este es el caso aquí es usted cómo puede hacer esto usando LINQ. Podría no ser la respuesta exacta, pero tratar de obtener la idea

    char[] Array1 = { 'a', 'b', 'c' };
    string[] Array2 = { "10", "20", "15" };

    var result = from i in Array1
                 from j in Array2
                   select i + j;

Estos artículos podrían ayudar

• SelectMany

• Cómo Utilizar LINQ SelectMany

El finalResult es el array deseado. Se asume que ambas matrices son del mismo tamaño.

char[] Array1 = { 'a', 'b', 'c' };
int[] Array2 = { 3, 2, 4 };

var finalResult = new List<string>();
finalResult.Add(String.Empty);
for(int i=0; i<Array1.Length; i++)
{
    var tmp = from a in finalResult
              from b in Enumerable.Range(1,Array2[i])
              select String.Format("{0} {1}{2}",a,Array1[i],b).Trim();
    finalResult = tmp.ToList();
}

Creo que esto será suficiente.

Aquí hay una versión de javascript, que estoy seguro de que alguien puede convertir. Ha sido probado a fondo.

Aquí está el violín.

function combinations (Asource){

    var combos = [];
    var temp = [];

    var picker = function (arr, temp_string, collect) {
        if (temp_string.length) {
           collect.push(temp_string);
        }

        for (var i=0; i<arr.length; i++) {
            var arrcopy = arr.slice(0, arr.length);
            var elem = arrcopy.splice(i, 1);

            if (arrcopy.length > 0) {
                picker(arrcopy, temp_string.concat(elem), collect);
            } else {
                collect.push(temp_string.concat(elem));
            }   
        }   
    }

    picker(Asource, temp, combos);

    return combos;

}

var todo = ["a", "b", "c", "d"]; // 5 in this set
var resultingCombos = combinations (todo);
console.log(resultingCombos);

Acabo de descubrir esta publicación de CodeProject que incluye Facetas.Combinatoria espacio de nombres que contiene algún código útil para manejar Permuaciones, Combinaciones y Variaciones en C#.

Http://www.codeproject.com/Articles/26050/Permutations-Combinations-and-Variations-using-C-G

Fon otra solución no basada en linq, más eficaz:

static IEnumerable<T[]> CartesianProduct<T>(T[][] arrays) {
    int[] lengths;
    lengths = arrays.Select(a => a.Length).ToArray();
    int Len = arrays.Length;
    int[] inds = new int[Len];
    int Len1 = Len - 1;
    while (inds[0] != lengths[0]) {
        T[] res = new T[Len];
        for (int i = 0; i != Len; i++) {
            res[i] = arrays[i][inds[i]];
        }
        yield return res;
        int j = Len1;
        inds[j]++;
        while (j > 0 && inds[j] == lengths[j]) {
            inds[j--] = 0;
            inds[j]++;
        }
    }
}