blog

A common situation: you are about to checkout at an online store, but before you can buy that new T-shirt you must first choose which color you want and select what size you wear.

You’ve likely never stopped to think about the data behind this simple interaction, but what really needs to happen is that based on these choices the application is actually selecting the specific inventory item you wish to purchase.

Let’s consider this same problem from the other side of the counter. Now, you are creating an online store and you have several lists of options that you must combine to form your inventory. How do you create every possible combination without missing any and without repeating? And, more importantly, how do you accomplish this programmatically so that store owner does not have to create each combo by hand (a task that quickly becomes overwhelming)?

In my elementary example you have a list of sizes {S, M, L, XL} and a list of colors {orange, red, blue, green}. Here it is quite simple: look at each color and make sure you have one item of each size for that color.


for( $i = 0; $i < count($colors); $i++ )
    for( $j = 0; $j < count($sizes); $j++)
        array_push( $combos, array( $colors[$i], $sizes[$j] ) );


But what if we have an unknown number of variables (maybe there is a third, or maybe there is a total of eight)? Our simple nested loop will no longer works when we don’t know how deep to go.

<mathspeak>

It helps to define this problem correctly, which is where the math comes in. Here, we have a finite number of finite sets and we wish to find all of the distinct ordered n-tuples who elements are the members of these sets. In other words, we want to find the Cartesian Product of the sets of our product options.

Symbolically…

if X₁, X₂, …, X_n are our sets of product options,

then, we want to calculate X₁ × X₂ × … × X_n = { (x₁, x₂, …, x_n) | x_i ∈ X_i }

This may look somewhat familiar from back in your days of graphing equations. The most common example of a Cartesian Product is what is called a Cartesian plane, or the x- and y- axes made up order pairs of numbers. Consider my original example, imagine labeling the x-axis with sizes and the y-axis with colors, the points then are your combinations. Same idea, just in more general terms.

</mathspeak>

Once we have the problem defined, we can tackle it programatically. My first reaction was to think recursion, but this problem can actually be solved quite elegantly in O(n²) time.

Click here to see my solution.

I made a cool little CSS discovery recently that I have already found to be quite powerful.

Using the class selector is done with the “.” character.

.foo { color: #ff0000; } makes any <div class=”foo” /> have red text. Likwise, .bar { font-size: 50px; } makes any <div class=”bar” /> have really really big text.

With CSS, it is possible to apply multiple classes to the same element by separating them with a space. In fact, <div class=”foo bar” /> will have really really big text that is also red in color.

But what I recently discovered is that it is possible to define a style that only applies to those elements that have all of the specified classes set. This means we can create a style that is only seen when an element has both class ‘foo’ AND class ‘bar.’

This is done like so,

.foo.bar { background-color: #ff00ff; }

Now, <div class=”foo” /> and <div class=”bar” /> will both take the background of their parent, but <div class=”foo bar” /> will have a rockin’ magenta background.

Pretty cool.

This is just a simple example. What is really going on here is that we are giving a style to a set of classes. And this style gets applied whenever that set is a subset of an element’s classes.

<div class=”a b c d e f”>Hello World.</div> (This element has a class set of {‘a’, ‘b’, ‘c’, ‘d’, ‘e’, ‘f’})

.c.b.a { color: #00cc00; } (This CSS style has a class set of {‘c’, ‘b’, ‘a’}).

Since {‘c’, ‘b’, ‘a’} ⊆ {‘a’, ‘b’, ‘c’, ‘d’, ‘e’, ‘f’}, our <div> will get this style.

Hmm, I feel a set theory post coming on.