This is an update to a post I originally published in February 2016, and shows how functional-programming wins out over imperative programming for writing this sort of algorithm.

The goal was: given a collection of things, eg “A”, “B” and “C”, get every possible combination, where a different order is considered a different combination, using C#.

So here we’d be looking for:

A AB AC ABC B BA BC BCA C CA CB CBA BCA CAB ACB

To cut to the chase, the best solution in C# I have come up with so far is:

using LanguageExt;
using static LanguageExt.Prelude;

public static class Combinations
{
    // eg Get(Seq("ABCDE")
    public static Seq<Seq<T>> Get<T>(Seq<T> source) =>
        source.Fold(
            state: new Seq<Seq<T>>(),
            folder: (state, t) =>
                state.Bind(item => Seq(item, t.Cons(item), item.Add(t))).Add(Seq1(t)));
}

This uses the language-ext library, described as “C# Functional Programming Language Extensions”.

To explain what this is doing, I’ll work backwards through applying it to strings, then not using language-ext, then using imperative programming.

A string is just an IEnumerable<char>, so the first method can be written for string only:

// Get("ABCDE")
public static Seq<string> Get(string source) =>
    source.Fold(
        state: new Seq<string>(),
        folder: (state, c) =>
            state.Bind(item => Seq(item, c + item, item + c)).Add(c.ToString()));

This in turn could be rewritten without using language-ext and just LINQ extensions:

public static IEnumerable<string> Get(string source) =>
    source.Aggregate(
        seed: new List<string>(),
        func: (acc, c) =>
        {
            var acc2 = acc.SelectMany(item =>
                new List<string> { item, c + item, item + c }).ToList();
            acc2.Add(c.ToString());
            return acc2;
        });

And finally, we could attempt a generic version just using LINQ:

public static IEnumerable<IEnumerable<T>> Get<T>(IEnumerable<T> source) =>
    source.Aggregate(
        seed: new List<List<T>>(),
        func: (acc, t) =>
        {
            var acc2 = acc.SelectMany(item =>
            {
                var prepended = new List<T>() { t };
                prepended.AddRange(item);

                var appended = new List<T>(item);
                appended.Add(t);

                return new List<List<T>> { item, prepended, appended };
            }).ToList();

            acc2.Add(new List<T> { t });
            return acc2;
        });
    }
One key difference is that language-ext types are immutable.  So when you use Add or Cons it will return a new list (here a Seq).  But for C#’s List<T> when you use Add it modifies the existing item and returns void.  So the code has to manage the process of creating a copy of each List, then prepending or appending an item, before adding it to the results.

Haskell

It is interesting that in Haskell, I can do all this in one line of code:
import Data.List
combinations :: [a] -> [[a]]
combinations xs = concatMap permutations $ subsequences xs
This is so succint partly because the Data.List module provides the permutations and subsequences functions that do what the C# code has to define for itself.
 

Below is my original post, showing how I tried to solve the problem with imperative programming in C#, and also a stab at F#.  Hopefully it is clear why my current approach using language-ext is better!

The original post (don’t copy this code!)

Published Feb 4, 2016

This is a simple C# algorithm that takes a sequence of characters and returns every possible combination of those characters.

The application for this was originally to test that a series of messages would be correctly handled by a message-consumer, regardless of the order in which they arrived (with a variation of the GetCombinations method taking in an IEnumerable<T> and returning an IEnumerable<IEnumerable<T>>).

class Program
{
    static void Main(string[] args)
    {
        var items = "ABCDEF";

        var combinations = GetCombinations(items)
            .Where(x => x.Length == items.Length)
            .ToList();

        foreach (var combination in combinations)
        {
            Console.WriteLine(combination);
        }

        Console.WriteLine($"Item count: {combinations.Count}");
        Console.WriteLine($"Distinct count: {combinations.Distinct().Count()}");

        Console.Read();
    }

    private static IEnumerable<string> GetCombinations(IEnumerable<char> items)
    {
        var combinations = new List<string> { string.Empty };

        foreach (var item in items)
        {
            var newCombinations = new List<string>();

            foreach (var combination in combinations)
            {
                for (var i = 0; i <= combination.Length; i++)
                {
                    newCombinations.Add(
                      combination.Substring(0, i) +
                      item +
                      combination.Substring(i));
                }
            }

            combinations.AddRange(newCombinations);
        }

        return combinations;            
    }
}

I also tried to do something similar in F# with my first draft as follows:

let rec getCombinations items memo =

    seq {
        for item in items do 
         let remainingItems = List.filter (fun i -> i <> item) items
         match remainingItems with
         | x::xs -> yield! getCombinations remainingItems (List.append memo [item])
         | [] -> yield List.append memo [item]         
    }

let results = getCombinations ["A"; "B"; "C"; "D"] []

Seq.iter (fun result -> printfn "%A" result) results

My F# code can definitely be improved on, but does illustrate how much terser F# can be over C# for these sort of algorithms.

Comments


Comments are closed