0 Comments
  •   Posted in: 
  • C#

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.

Post comment