Kombinationsgenerator in Linq

Question

Ist es möglich, einige Linq zu erstellen, die eine Liste erzeugt, die alle möglichen Kombinationen einer Reihe von Zahlen enthält?

Bei der Eingabe von „21“ eine Liste mit den Elementen erzeugen würde:

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

(nessesarily nicht in dieser Reihenfolge)

Ich verstehe Sie Bereich verwenden können Dinge wie:

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

Welche generiert das Alphabet von az. Aber ich kann nicht scheinen, dieses Wissen zu übertragen, um einen Kombinationsgenerator

zu machen Ich bin in der Lage, es mit dem folgenden Code herauszufinden, aber es scheint viel zu sperrig und ich bin sicher, dass es mit ein paar Zeilen getan werden kann. Es fühlt sich wirklich wie eine schlechte Lösung an, die ich gemacht habe.

Stellen Sie sich vor ich GetAllCombinations("4321") genannt, wenn es

hilft

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

Für das, was es wert ist, versuchen, etwas wie folgt aus:

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

Was Sie suchen tatsächlich Permutationen sind. Kurz gesagt bedeutet Permutation, dass die Reihenfolge relevant ist (dh 12 ist anders als 21), während eine Kombination bedeutet, dass die Reihenfolge irrelevant ist (12 und 21 sind äquivalent). Für weitere Informationen siehe Wikipedia.

Siehe this thread.

Was tut in reiner LINQ ist, die für die Zwecke der Verwendung von LINQ wie mit LINQ-Sounds.

Answer 3

Für das Protokoll: Joshs Antwort die allgemeine Art und Weise:

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 4

Hier ist meine Permutation und Kombination Funktion 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); 
} 

Für das DNA-Alphabet 'A', 'C', 'G', 'T':

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

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

gibt

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

und die Kombinationen (k = 2) von DNA-Alphabet

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

sind

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

Answer 5

Wie andere haben die Lösungen auf dieser Seite darauf hingewiesen, erzeugt Duplikate, wenn eines der Elemente identisch ist. Die Erweiterung Distinct() entfernt sie, aber sie ist nicht sehr skalierbar, da dies normalerweise dazu führt, dass der gesamte Suchbaum trotzdem durchlaufen wird.Sie werden den Suchraum trimmen erheblich, indem sie es während Traversal Aufruf:

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

Für das Beispiel string „bananabana“ führt dies zu 8294 Knoten besucht wird, als besuchte zum 9.864.101 Gegensatz, wenn Sie das nicht tun Traversal Culling .