Cardinality and Bit Patterns

originally published on January 14, 2021

We just recently celebrated the feast of Epiphany, but this week I had an epiphany all my own, something I hadn’t realized before. It has to do with math and sets and bit patterns, some of my favorite things, but let me start at the beginning. That’s a very good place to start.

Once upon a time I learned that the cardinality of the Power Set of a set A with n members is 2ⁿ or C(P(A)) = 2ⁿ. The cardinality is simply the number of items in a set, and the Power set is the set of all possible subsets of a given set.

For example, if my starting set A = {a, b, c}, then the Power set of A is

P(A) = {{}, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}}

You can see that this set of all possible sets has a cardinality of 2³ = 8 and includes the empty set, all sets with one member, all sets with two members, and the set with all three members. In the language of Combinatorics (the mathematics of counting), the cardinality of the Power set is the sum of the number of Combinations of 3 things taken 0 at a time + the number of Combinations of 3 things taken 1 at a time + the number of Combinations of 3 things taken 2 at a time + the number of Combinations of 3 things taken 3 at a time. More succinctly:

C(P(A)) = C(3, 0) + C(3, 1) + C(3, 2) + C(3, 3)

That’s very nice. But how did we get that neat formula of 2ⁿ?

Well, remember the Binomial Theorem? That’s how!

The Binomial Theorem defines the expansion of the binomial expression (a + b)ⁿ into n + 1 terms. And it just so happens that the coefficients of each ab term are those Combinations: C(n, 0), C(n, 1), C(n, 2), … C(n, n). Awesome!, so just set a = b = 1 and it falls out:

(1 + 1)ⁿ = 2ⁿ = C(n, 0) + C(n, 1) + C(n, 2) + … + C(n, n)

There you are! Very cool. But that’s not what my epiphany was.

In a recent project, the Money Converter Problem Solver, I wanted to manipulate all possible coin combinations of a universal set of coins, in effect creating a Power set of all coin combinations.

First, define the set Money as {dollars, halfs, quarters, dimes, nickels, pennies}. Then generate all possible subsets, including {pennies}, {nickels}, {nickels, pennies}, {dimes}, {dimes, pennies}, {dimes, nickels}, {dimes, nickels, pennies}, and so on. There would be 2⁶ – 1 = 63 such sets (subtract one because the empty set should be thrown out).

Question: How do you compactly generate all these sets in code?

Answer: Count in binary!

Using a regular for loop running from 1 to 63, convert the decimal number to binary and zero pad to the left to create a binary bit pattern of 6 bits. This pattern indicates which currency unit to use (indicated by 1) and which not to use (indicated by 0). Since n bits in a row create 2ⁿ possibilities (but we’re excluding the empty set by starting at 1), we’ve accounted for all possible combinations, which is the same as all subsets of the Power set!

In pseudo code, we might write it like this:

// loop through all possibilities in decimal
for n = 1 to 63
  // convert the decimal number to a left zero-padded pattern
  // to selectively choose or not choose each unit thereby
  // generating all possibilities 
  let b = n.toString(2).padStart(6, '0'); // 000001, 000010,
    // now use the pattern to build each subset
.
.
.

Well, of course! It’s so obvious. But sometimes the obvious is not so much so, at least for this old codger.