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.