Algorithm: Find All Unique Combinations in a List

My son, Benson Joeris, just showed me a rather cool algorithm that I thought I’d share. I’m really, really lucky to have an algorithms genius on speed dial. I thought this solution was cool because I tend to think of active solutions to problems, not mapping them onto a structure – IOW, this represented a very different approach to the algorithm than I think I would have arrived at.

The goal: Given any list

A, B, C, …

I want to find all combinations, with no duplicates (assuming there are no duplicates in the original list).

<emptySet>

A

B

C

A,B

A,C

A,B,C

I thought of a few rather bizarre approaches before sending Benson an email…

It sounds like you want to enumerate subsets of {1,…,N}. There are 2^N of these, and they can fairly easily be encoded as the integers 1,…,(2^N)-1, by thinking about the numbers in binary. If the least significant bit is 1, then string 1 is included, and if it is 0, string 1 is not included. The next least significant bit encodes whether string 2 is included, and so on. So, with a little bit manipulation, you can decode an integer into the string arrays you are looking for, and then just have to loop over 1,…,(2^N)-1 (or 0,…,(2^N)-1, if you want to include the empty set of strings)

I wrote this up

.csharpcode, .csharpcode pre
{
font-size: small;
color: black;
font-family: consolas, “Courier New”, courier, monospace;
background-color: #ffffff;
/*white-space: pre;*/
}
.csharpcode pre { margin: 0em; }
.csharpcode .rem { color: #008000; }
.csharpcode .kwrd { color: #0000ff; }
.csharpcode .str { color: #006080; }
.csharpcode .op { color: #0000c0; }
.csharpcode .preproc { color: #cc6633; }
.csharpcode .asp { background-color: #ffff00; }
.csharpcode .html { color: #800000; }
.csharpcode .attr { color: #ff0000; }
.csharpcode .alt
{
background-color: #f4f4f4;
width: 100%;
margin: 0em;
}
.csharpcode .lnum { color: #606060; }in C# as

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

// 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()));

// Start at 1 if you do not want the empty set
for (int mask = 0; mask < setCount; mask++)
{
var nestedList = new List<T>();
for (int j = 0; j < initialList.Count(); j++)
{
// Each position in the initial list maps to a bit here
var pos = 1 << j;
if ((mask & pos) == pos) { nestedList.Add(initialList[j]); }
}
ret.Add(nestedList);
}
return ret;
}




This will contain exactly the set I was looking for!



If you’d like me to do a post explaining why this works, let me know.



[ Edit: This was requested and appears here. ]



I’m including the download of the code and associated tests.

5 thoughts on “Algorithm: Find All Unique Combinations in a List”

  1. Neat algorithm. I do a similar thing in parts of our software where we have a hierarchy of configurations for doctors, anaesthetists, procedure types, etc and there can be configurations on each permutation (not combination) of them. Thinking of them as a series of bits and using AND/OR for bitmasking made it quite easy to develop an algorithm and also make sure that overrides (a rule specified for a doctor & procedure should be respected over a rule specified for the doctor alone).

  2. Seems like you should mention that if your list contains more items than the number of bits in your “int” (probably 32 or 64) then this approach will not work – at least not without moving from native ints to a BigInt or BitVector class that supports bitwise operations. Given the number of subsets, you could also “yield return” each subset list so you don’t make a concrete collection of all the subsets as you consume them.

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>