Linq Combined Generator

Question

Is it possible to create some Linq that generates a list containing all possible combinations of a series of numbers?

If you enter "21", it will generate a list with elements:

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

(Not necessarily in that order)

I understand that you can use a range to do things like:

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

What generates the alphabet from az. But I can not transfer this knowledge to create a combination generator

I was able to figure out the following code, but it seems too cumbersome, and I'm sure it can be done with a few lines. It really seems like the bad decision I made.

Imagine what I called GetAllCombinations("4321") if it helps

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

Answer 1

For what it's worth, try something like this:

 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

For the record: Josh will answer the general path:

 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

Here is my Permutation and Combination function using 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); } 

For the DNA alphabet "A", "C", "G", "T":

 var dna = new[] {'A', 'C', 'G', 'T'}; foreach (var p in dna.Permutate()) Console.WriteLine(String.Concat(p)); 

gives

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

and combinations (k = 2) of the DNA alphabet

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

are

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

Answer 4

What you are looking for is permutations. In short, permutations mean that order matters (i.e. 12 is different from 21), while order of combinations doesn't matter (12 and 21 are equivalent). For more information, see Wikipedia.

Watch this stream.

Regarding the execution in pure LINQ, it is similar to using LINQ to use LINQ.

Answer 5

As others pointed out, the solutions on this page will generate duplicates if any of these elements are the same. The Distinct () extension will remove them, but it is not very scalable, as this will usually cause the entire search tree to go through anyway. You will significantly trim your search space by calling it during a crawl:

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

In the bananabana line example, this results in a visit to 8,294 nodes, as opposed to 9,864,101 visited when you are not crawling.