Linq的组合发电机

是否有可能创建一些Linq,生成一个包含一系列数字的所有可能组合的List?

如果输入“21”,它将生成一个包含以下元素的列表:

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

(不按顺序)

我知道你可以使用范围来做以下事情:

 List 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. eg 1-2-3-4 have 24 different combinations { int result = 1; for (int i = 1; i <= n; i++) result *= i; return result; } 

为了它的价值,尝试这样的事情:

 public static IEnumerable 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 }; } 

为了记录:Josh回答了通用的方式:

 public static IEnumerable> GetPermutations(IEnumerable 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}; } } 

这是我使用Linq的Permutation和Combinationfunction

 public static IEnumerable Prepend(this IEnumerable source, TSource item) { if (source == null) throw new ArgumentNullException("source"); yield return item; foreach (var element in source) yield return element; } public static IEnumerable> Permutate(this IEnumerable 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> Combinate(this IEnumerable 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(); 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 

您正在寻找的实际上是排列。 简而言之,排列意味着顺序是相关的(即,12与21不同),而组合意味着顺序是无关紧要的(12和21是等价的)。 有关更多信息,请参阅Wikipedia。

看到这个post。

至于在纯LINQ中做的事情,听起来就像使用LINQ一样使用LINQ。

正如其他人指出的那样,如果任何元素相同,则此页面上的解决方案将生成重复项。 Distinct()扩展将删除它们,但它不是很可扩展,因为它通常会导致遍历整个搜索树。 您将通过在遍历期间调用它来显着缩小搜索空间:

 private static IEnumerable 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个节点,而不是在不进行遍历剔除时访问的9,864,101个节点。