Linq中的組合發生器

Question

是否可以創建一些Linq來生成包含一系列數字的所有可能組合的List？

如果輸入「21」，它會產生與元素的列表：

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

（不nessesarily順序）

我知道你可以使用範圍做這樣的事情：

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

它從az生成字母表。但我似乎無法將這些知識轉化爲組合生成器

我已經能夠用下面的代碼弄明白了，但它看起來太笨重了，我相信它可以用幾行來完成。它確實感覺我是一個糟糕的解決方案。

想象我呼籲GetAllCombinations("4321")如果它可以幫助

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

對於它的價值，嘗試這樣的事情：

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

你在找什麼，實際上排列。簡而言之，排列意味着訂單是相關的（即，12與21不同），而組合意味着訂單不相關（12和21是等同的）。欲瞭解更多信息，請參閱Wikipedia.

見this thread.

至於做的是純LINQ，這聽起來像使用LINQ使用LINQ的緣故。

Answer 3

爲了記錄在案：Josh的答案的一般方法：

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

下面是使用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); 
} 

對於DNA字母'A'，'C'，'G'，'T'：

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

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

給出

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

和組合DNA字母表（K = 2）

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

是

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

Answer 5

正如其他人指出了這個頁面上的解決方案如果任何元素相同，將會生成重複項。 Distinct（）擴展將刪除它們，但它不具有可伸縮性，因爲它通常會導致整個搜索樹被遍歷。

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

對於例如字符串「bananabana」這將導致8,294節點被訪問，而不是訪問時你不這樣做遍歷撲殺9864101：您可以通過遍歷期間調用它大大修剪的搜索空間。