Explanation of Finding All Unique Combinations in a List

I showed an algorithm for finding all unique combinations of items in a list here.

I didn’t know whether the explanation would be interesting, so I simply offered to add it if someone wanted to see it. Someone did, so here goes.

Theory

Imagine first the problem on paper. Make a column for each item in the list – four is a good place to start and then you can generalize it upwards. The list will look something like this:

ComboAlgorithmExplanation1

I’ll update this grid to use the number 1 as an x, and add a column for no items, because the empty set is important for the problem I’m solving:

ComboAlgorithmExplanation2

And then assign each column to a bit. This makes each of the numbers from 0 to 15 a bit mask for the items to select to make that entry in the unique set.

ComboAlgorithmExplanation3

Code

The code creates a List of Lists because the problem I was solving was combinations of objects, not strings. I should have used IEnumerable here, as the returned list won’t be changed.

public static List<List<T>> GetAllCombos<T>(this List<T> initialList)
{
   var ret = new List<List<T>>();


I’m not sure about the mathematical proof for this, but the number of items is always 2^N (two to the power of N) or 2^N – 1 if you’re ignoring the empty set.

   // The final number of sets will be 2^N (or 2^N - 1 if skipping empty set)
   int setCount = Convert.ToInt32(Math.Pow(2, initialList.Count()));


When I started this post, I realized I’d left the Math.Pow function in this first call, so I’ll explain the difference. Math.Pow takes any value as a double data type and raises it to the power of another double. Doubles are floating points, making this a very powerful function. But in the special case of 2^N, there’s a much faster way to do this – perhaps two orders of magnitude faster. This doesn’t matter if you are only calling it once, but it is sloppy. Instead, I should have done a bit shift.

   var setCount = 1 << initialList.Count();


This bit shift operator takes the value of the left operand (one) and shifts it to the left. Thus if the initial count is zero, no shift is done, and there will be one resulting item, the empty list. If there are two items, the single bit that is set (initially 1) is shifted twice, and the result is 4:

ComboAlgorithmExplanation4

Since each number is an entry in my set of masks, I iterate over the list (setCount is 16 for four items):

   // Start at 1 if you do not want the empty set
   for (int mask = 0; mask < setCount; mask++)
   {


For my purposes, I’m creating a list – alternatively, you could build a string or create something custom from the objects in the list (a custom projection).

      var nestedList = new List<T>();


I then iterate over the count of initial items (4 for four items) – this corresponds to iterating over the columns of the grid:

      for (int j = 0; j < initialList.Count(); j++)
      {


For each column, I need the value of that bit position – the value above the letter in the grids above. I can calculate this using the bit shift operator. Since this operation will be performed many times, you definitely want to use bit shift instead of Math.Pow here:

          // Each position in the initial list maps to a bit here
          var pos = 1 << j;


I use a bitwise And operator to determine whether the bit is set, for each item in the list. If the mask has the bit in the position j set, then that entry in the initial list is added to the new nested list.

         if ((mask & pos) == pos) { nestedList.Add(initialList[j]); }
      }


Finally, I add the new nested list to the lists that will be returned, and finish out the loops.

      ret.Add(nestedList);
   }
   return ret;
}



Questions?

One thought on “Explanation of Finding All Unique Combinations in a List”

  1. Thank you for the explanation. The algorithm is indeed ingeniously simple. Calls to Convert.ToString(mask, 2) and Convert.ToString(pos, 2) helped a lot to visualize what’s happening by converting the int’s into their binary representation. Once again, thanks!

Leave a Reply

Your email address will not be published. Required fields are marked *


*

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>