# 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. Eugene says:

Since you were so nice to offer… would you please explain why this works? Thanks!

3. Kathleen says:

Eugene,

I just posted the explanation of the algorithm.

Kathleen

4. MBR says:

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.

5. Kathleen says:

MBR,

Excellent points!

Kathleen