Combination Generator in Linq

Question

E 'possibile creare un Linq che genera una lista contenente tutte le possibili combinazioni di una serie di numeri ??

Se si immette "21" Sarebbe generare un elenco con gli elementi:

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

(Non nessesarily in questo ordine)

ho capito si può usare gamma di fare cose come:

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

Che genera l'alfabeto da az. Ma non riesco a trasferire questa conoscenza per creare un generatore di combinazioni

Sono stato in grado di capire con il seguente codice, ma sembra troppo ingombrante e sono sicuro che può essere fatto con poche righe. Mi sembra davvero una cattiva soluzione che ho fatto.

Immaginate che ho chiamato GetAllCombinations("4321") se aiuta

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

Per quel che vale, provare qualcosa di simile:

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

Cosa state cercando sono in realtà permutazioni. In breve, permutazioni significa che l'ordine è rilevante (cioè 12 è diverso da 21) mentre una combinazione significa che l'ordine è irrilevante (12 e 21 sono equivalenti). Per ulteriori informazioni, vedere Wikipedia.

Vedi this thread.

Per quanto riguarda facendo è in puro LINQ, che suona come utilizzare LINQ per il bene di usare LINQ.

Answer 3

Per la cronaca: la risposta di Josh modo generico:

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

Qui è la mia funzione di permutazione e la combinazione utilizzando 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); 
} 

Per l'alfabeto del DNA "A", "C", "G", "T":

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

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

dà

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

e le combinazioni (k = 2) di alfabeto DNA

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

sono

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

Answer 5

Come altri hanno sottolineato le soluzioni a questa pagina genererà duplicati se uno qualsiasi degli elementi è lo stesso. L'estensione Distinct() le rimuoverà, ma non è molto scalabile in quanto di solito provoca l'attraversamento dell'intero albero di ricerca.Potrai tagliare lo spazio di ricerca notevolmente invocando durante l'attraversamento:

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

Ad esempio, la stringa "bananabana" questo si traduce in 8.294 nodi di essere visitato, in contrapposizione al 9.864.101 visitato quando non si fa attraversamento abbattimento .