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. 
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) { permutation.Add(item); } i++; bitIndex = (int)Math.Pow(2, i - 1); } permutations.Add(permutation); } private static int GetTop(int count) { int result = 0; for (int i = 0; i < count; i++) { result = (result << 1) + 1; } return result; } } }
).
Neil Barnwell
