Combination Generator in Linq

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 would generate a list with the elements:

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

(Not nessesarily in that order)

I understand you can use 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

Which generates the alphabet from a-z. But I can not seem to transfer this knowledge to make a combination generator

I have been able to figure it out with the following code, but it seems way too bulky and I am sure it can be done with a few lines. It really does feel like a bad solution I have made.

Imagine I have 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. e.g 1-2-3-4 have 24 different combinations
{
    int result = 1;

    for (int i = 1; i <= n; i++)
        result *= i;

    return result;
}

Jampacked

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

Schwarz

Just to note, this function as given doesn't do what the question asks. (It generates { "12", "21" }, missing "11" and "22".) I can only assume the asker did manage to adapt it into something useful. – Locris

This code also doesn't work if there are duplicate characters in the string. If the string contains "banana", the second call to IndexOf('a') in the for-loop will return the first 'a' again. – Deedee

Answer 2

For the record: Josh's answer the generic way:

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

Edmondo

A word of caution: This won't work if two or more elements in items are equal. – Malamud

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 the combinations (k = 2) of 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

Excursion

Lovely, needed the number of combinations part :D – Gristede

your combination part is not working correct as it producing identical combination sets - in your example you can see 'AC' and 'CA', or another example 'AG' and 'GA' - what you producing in combinate is actually something else which is called variations. combinate should treat 'AC' and 'CA' as same thing and so only return one of those. Other than that I really enjoyed studying your code :) – Artwork

Your 'Combinate' method does an operation that is called 'partial permutation' – Nunci

Answer 4

What you're looking for are actually permutations. In short, permutations means that order is relevant (ie, 12 is different from 21) whereas a combination means order is irrelevant (12 and 21 are equivalent). For more information see Wikipedia.

See this thread.

As for doing is in pure LINQ, that sounds like using LINQ for the sake of using LINQ.

Campus

Well I mentioned LINQ because they are usually 1 or 2 lines -> which I want to archive as I hate me enormous method – Jampacked

Answer 5

As others have pointed out the solutions on this page will generate duplicates if any of the elements are the same. The Distinct() extension will remove them, but it's not very scalable as it will usually result in the entire search tree being traversed anyway. You'll trim the search space considerably by invoking it during traversal:

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

For the example string "bananabana" this results in 8,294 nodes being visited, as opposed to the 9,864,101 visited when you don't do traversal culling.

Ulick

Answer 6

You can use this Permute LINQ extension:

foreach (var value in Enumerable.Range(1,3).Permute())
  Console.WriteLine(String.Join(",", value));

Which results in this:

1,1,1
1,1,2
1,1,3
1,2,1
1,2,2
1,2,3
1,3,1
1,3,2
1,3,3
2,1,1
2,1,2
2,1,3
2,2,1
2,2,2
2,2,3
2,3,1
...

You can optionally specify the # of permutations

foreach (var value in Enumerable.Range(1,2).Permute(4))
  Console.WriteLine(String.Join(",", value));

Results:

1,1,1,1
1,1,1,2
1,1,2,1
1,1,2,2
1,2,1,1
1,2,1,2
1,2,2,1
1,2,2,2
2,1,1,1
2,1,1,2
2,1,2,1
2,1,2,2
2,2,1,1
2,2,1,2
2,2,2,1
2,2,2,2

Extension Class to add:

public static class IEnumerableExtensions
{
  public static IEnumerable<IEnumerable<T>> Permute<T>(this IEnumerable<T> values) => values.SelectMany(x => Permute(new[] { new[] { x } }, values, values.Count() - 1));
  public static IEnumerable<IEnumerable<T>> Permute<T>(this IEnumerable<T> values, int permutations) => values.SelectMany(x => Permute(new[] { new[] { x } }, values, permutations - 1));
  private static IEnumerable<IEnumerable<T>> Permute<T>(IEnumerable<IEnumerable<T>> current, IEnumerable<T> values, int count) => (count == 1) ? Permute(current, values) : Permute(Permute(current, values), values, --count);
  private static IEnumerable<IEnumerable<T>> Permute<T>(IEnumerable<IEnumerable<T>> current, IEnumerable<T> values) => current.SelectMany(x => values.Select(y => x.Concat(new[] { y })));
}

Apocrine