Disclaimer: I know those of you who’ve done computer science or software engineering at university will already know how to do this, and know the name for the pattern, but in case we don’t use it I wanted to show it off somewhere. Smile

A colleague and I just had a code-off without realising it; we were both thinking about the same problem at the same time. That problem being a way to take a list of things, and get a list of the permutations of them.

So { “P1”, “P2”, “P3” } should result in:

    { “P1” },
    { “P2” },
    { “P3” },
    { “P1”, “P2” },
    { “P1”, “P3” },
    { “P2”, “P3” },
    { “P1”, “P2”, “P3” }

I remembered an trick an old boss of mine taught me for finding combinations of items in a series, using bits. If you think of iterating a series of bytes you see the usual pattern:

  • 1 = 00000001
  • 2 = 00000010
  • 3 = 00000011
  • 4 = 00000100

So this means that iterating a numeric value (i.e. 1 to 256) and converting the loop variable to a sequence of bits on each iteration is basically going to generate all the combinations of true and false for a series of 8 boolean flags. That’s the behaviour we’re looking for. Of course, 8 is quite a limitation, but if we use Integer rather than byte we get 32, which is more than enough (in fact I get OutOfMemoryExceptions with a series of 23 items on my 8gig Quad-Xeon machine).

Here’s my implementation. Notice I’m using the trick, but I’m not iterating all the “powers of 2”, I’m iterating the items in a list, and only taking the ones where the bit representing their position in the list is set:

using System;
using System.Collections.Generic;

namespace ConsoleApplication13
    public class Combinator
        public IList<List<T>> AllCombinationsOf<T>(IList<T> items)
            if (items == null) throw new ArgumentNullException("items");
            if (items.Count > 32) throw new ArgumentException("Only 32 values are supported.", "items");

            int top = GetTop(items.Count);

            var permutations = new List<List<T>>();
            for (int combinationId = 1; combinationId <= top; combinationId++)
                AddPermutations(permutations, combinationId, items);

            return permutations;

        private static void AddPermutations<T>(List<List<T>> permutations, int filter, IEnumerable<T> items)
            var permutation = new List<T>();

            int i = 1;
            int bitIndex = 1;
            foreach (var item in items)
                if ((filter & bitIndex) == bitIndex)

                bitIndex = (int)Math.Pow(2, i - 1);


        private static int GetTop(int count)
            int result = 0;
            for (int i = 0; i < count; i++)
                result = (result << 1) + 1;
            return result;

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s