Generador de combinación en LINQ

Question

¿Es posible crear un poco de LINQ que genera una lista que contiene todas las combinaciones posibles de una serie de números ??

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

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

(No nessesarily en ese orden)

Yo entiendo que puede utilizar rango de hacer cosas como:

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

¿Qué genera el alfabeto de una-z. Pero me parece que no puede transferir este conocimiento para hacer un generador de combinación

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

Imagínese que he llamado 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

Por lo que vale, intentar 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 };
}

Answer 2

Para el registro: Josh a responder a la forma 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 3

Aquí está mi Permutación y combinación función utilizando 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 del 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 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 4

Lo que estamos 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 orden es irrelevante (12 y 21 son equivalentes). Para obtener más información, consulte Wikipedia.

este hilo.

En cuanto a hacer es puro en LINQ, que suena como el uso de LINQ en aras de utilizar LINQ.

Answer 5

Como otros han señalado las soluciones en esta página va a generar duplicados si alguno de los elementos son los mismos. La extensión distinta () eliminará ellos, pero no es muy escalable, ya que dará lugar generalmente a todo el árbol de búsqueda atravesada de todos modos. Vas a recortar el espacio de búsqueda considerablemente mediante la invocación 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;
}

Por ejemplo, la cadena "bananabana" esto se traduce en 8.294 nodos que se visitaron, en contraposición al 9864101 visitado cuando no lo hace el sacrificio de recorrido.

Answer 6

Puede utilizar esta extensión Permute LINQ:

foreach (var value in Enumerable.Range(1,3).Permute())
  Console.WriteLine(String.Join(",", value));

que se traduce en lo siguiente:

1,1,1
1,1,2
1,1,3
1,2,1
1,2,2
1,2,3
1,3,1
1,3,2
1,3,3
2,1,1
2,1,2
2,1,3
2,2,1
2,2,2
2,2,3
2,3,1
...

Opcionalmente, puede especificar el # de permutaciones

foreach (var value in Enumerable.Range(1,2).Permute(4))
  Console.WriteLine(String.Join(",", value));

Resultados:

1,1,1,1
1,1,1,2
1,1,2,1
1,1,2,2
1,2,1,1
1,2,1,2
1,2,2,1
1,2,2,2
2,1,1,1
2,1,1,2
2,1,2,1
2,1,2,2
2,2,1,1
2,2,1,2
2,2,2,1
2,2,2,2

Clase de extensión para añadir:

public static class IEnumberableExtensions
{
  public static IEnumerable<IEnumerable<T>> Permute<T>(this IEnumerable<T> values) => values.SelectMany(x => Permute(new[] { new[] { x } }, values, values.Count() - 1));
  public static IEnumerable<IEnumerable<T>> Permute<T>(this IEnumerable<T> values, int permutations) => values.SelectMany(x => Permute(new[] { new[] { x } }, values, permutations - 1));
  private static IEnumerable<IEnumerable<T>> Permute<T>(IEnumerable<IEnumerable<T>> current, IEnumerable<T> values, int count) => (count == 1) ? Permute(current, values) : Permute(Permute(current, values), values, --count);
  private static IEnumerable<IEnumerable<T>> Permute<T>(IEnumerable<IEnumerable<T>> current, IEnumerable<T> values) => current.SelectMany(x => values.Select(y => x.Concat(new[] { y })));
}