c# - Generador Combinado en Linq

combinations

Question

¿Es posible crear algún Linq que genere una Lista que contenga todas las combinaciones posibles de una serie de números?

Si ingresas "21" generaría una lista con los elementos:

list[0] = "21"
list[1] = "22"
list[2] = "11"
list[3] = "12"

(No necesariamente en ese orden)

Entiendo que puedes usar el rango para hacer cosas como:

List<char> letterRange = Enumerable.Range(''a'', ''z'' - ''a'' + 1).Select(i => (Char)i).ToList(); //97 - 122 + 1 = 26 letters/iterations

Lo que genera el alfabeto a partir de az. Pero parece que no puedo transferir este conocimiento para hacer un generador de combinación

He podido averiguarlo con el siguiente código, pero parece demasiado voluminoso y estoy seguro de que se puede hacer con unas pocas líneas. Realmente se siente como una mala solución que he hecho.

Imagina que he llamado a GetAllCombinations("4321") si ayuda

public static String[] GetAllCombinations(String s)
{
    var combinations = new string[PossibleCombinations(s.Length)];

    int n = PossibleCombinations(s.Length - 1);

    for (int i = 0; i < s.Length; i++)
    {
        String sub;
        String[] subs;

        if (i == 0)
        {
            sub = s.Substring(1); //Get the first number
        }
        else if (i == s.Length - 1)
        {
            sub = s.Substring(0, s.Length - 1);
        }
        else
        {
            sub = s.Substring(0, i) + s.Substring(i + 1); 
        }

        subs = GetAllCombinations(sub);

        for (int j = 0; j < subs.Length; j++)
        {
            combinations[i * n + j] = s[i] + subs[j];
        }
    }

    return combinations;
}
public static int PossibleCombinations(int n) //Combination possibilities. e.g 1-2-3-4 have 24 different combinations
{
    int result = 1;

    for (int i = 1; i <= n; i++)
        result *= i;

    return result;
}

Answer 1

Aquí está mi función de Permutación y Combinación usando Linq

public static IEnumerable<TSource> Prepend<TSource>(this IEnumerable<TSource> source, TSource item)
{
    if (source == null)
        throw new ArgumentNullException("source");

    yield return item;

    foreach (var element in source)
        yield return element;
}

public static IEnumerable<IEnumerable<TSource>> Permutate<TSource>(this IEnumerable<TSource> source)
{
    if (source == null)
        throw new ArgumentNullException("source");

    var list = source.ToList();

    if (list.Count > 1)
        return from s in list
                from p in Permutate(list.Take(list.IndexOf(s)).Concat(list.Skip(list.IndexOf(s) + 1)))
                select p.Prepend(s);

    return new[] { list };
}

public static IEnumerable<IEnumerable<TSource>> Combinate<TSource>(this IEnumerable<TSource> source, int k)
{
    if (source == null)
        throw new ArgumentNullException("source");

    var list = source.ToList();
    if (k > list.Count)
        throw new ArgumentOutOfRangeException("k");

    if (k == 0)
        yield return Enumerable.Empty<TSource>();

    foreach (var l in list)
        foreach (var c in Combinate(list.Skip(list.Count - k - 2), k - 1))
            yield return c.Prepend(l);
}

Para el alfabeto de ADN ''A'', ''C'', ''G'', ''T'':

var dna = new[] {''A'', ''C'', ''G'', ''T''};

foreach (var p in dna.Permutate())
    Console.WriteLine(String.Concat(p));

da

ACGT ACTG AGCT AGTC ATCG ATGC CAGT CATG CGAT CGTA CTAG CTGA GACT GATC GCAT GCTA GTAC GTCA TACG TAGC TCAG TCGA TGAC TGCA

y las combinaciones (k = 2) del alfabeto de ADN

foreach (var c in dna.Combinate(2))
        Console.WriteLine(String.Concat(c));

son

AA AC AG AT CA CC CG CT GA GC GG GT TA TC TG TT

Answer 2

Como otros han señalado, las soluciones en esta página generarán duplicados si alguno de los elementos es el mismo. La extensión Distinct () los eliminará, pero no es muy escalable, ya que generalmente resultará en que se recorra todo el árbol de búsqueda de todos modos. Recortará el espacio de búsqueda considerablemente invocándolo durante el recorrido:

private static IEnumerable<string> Permute(string str)
{
    if (str.Length == 0)
        yield return "";
    else foreach (var index in str.Distinct().Select(c => str.IndexOf(c)))
        foreach (var p in Permute(str.Remove(index, 1)))
            yield return str[index] + p;
}

Para la cadena de ejemplo "bananabana", esto da como resultado que se visiten 8.294 nodos, a diferencia de los 9.864.101 visitados cuando no se realiza el sacrificio transversal.

Answer 3

Lo que estás buscando son en realidad permutaciones. En resumen, permutaciones significa que el orden es relevante (es decir, 12 es diferente de 21) mientras que una combinación significa que el orden es irrelevante (12 y 21 son equivalentes). Para más información vea Wikipedia.

Ver este hilo.

En cuanto a hacer está en LINQ puro, eso suena como usar LINQ por el simple hecho de usar LINQ.

Answer 4

Para el registro: Josh responde de manera genérica:

public static IEnumerable<IEnumerable<T>> GetPermutations<T>(IEnumerable<T> items) {
        if (items.Count() > 1) {
            return items.SelectMany(item => GetPermutations(items.Where(i => !i.Equals(item))),
                                   (item, permutation) => new[] { item }.Concat(permutation));
        } else {
            return new[] {items};
        }
    }

Answer 5

Para lo que vale la pena, intente algo como esto:

public static IEnumerable<string> GetPermutations(string s)
{
    if (s.Length > 1)
        return from ch in s
               from permutation in GetPermutations(s.Remove(s.IndexOf(ch), 1))
               select string.Format("{0}{1}", ch, permutation);

    else
        return new string[] { s };
}