Permutations and Combinations

In the last couple years I’ve regained interest in solidifying my math chops. One mathematical concept that I see popping up again and again is that of permutations and combinations. I tried searching around for quick explanations, but I wasn’t really pleased with what I found. I thought I would share an approach that really helped me get it.

Permutations

Finding the number of permutations of a unique set is simple, but tricky to understand. Once it “clicks,” you’ll think to yourself, “why did I think that was so hard?” (if you’re like me anyways).

Given a set with unique elements, you can permute it by mixing up the elements. Finding the permutations of a set involves figuring out all the unique ways you can mix those elements. The key concept in a permutation is ordering: it matters how the elements are ordered. Thus, the permutation \left \{ab \right \} is distinct from \left \{ba \right \}. The question, “how many permutations are there of a set?”, is asking for all possible orderings of the elements in that set. Consider the set:

S = \left \{abc \right \}

What are all the permutations of S? One way to do this by hand is by picking an element to go first and enumerating the permutations of the remaining elements:

(a goes first)

\left \{abc \right \} \left \{acb \right \}

(b goes first)

\left \{bac \right \} \left \{bca \right \}

(c goes first)

\left \{cab \right \} \left \{cba \right \}

As you can see, there are 6 permutations of this set. One thing to notice is that there are 3 members in the set, and we could pick any of those to be the first element. More generally, given N elements in a set, there are N ways to pick the first element.

But what about the second element? Assuming all members are unique, we can take the subset of N-1 elements and pick any of those to be the second. For example, let’s assume we’ve picked a already, we’re left with a subset of S without a:

\left \{bc \right \}

This particular set is trivial, but let’s stick with our plan:

(b goes first)

\left \{bc\right \}

(c goes first)

\left \{cb \right \}

We end up with only two permutations of this subset. More generally, we’ve got N-1 elements, and we can pick any of those to go first in our subset.

You may be spotting a pattern here, and that’s the key insight. We started with N elements, and we’re free to pick any one of those to go first. Then, for every one of those N choices, we have a subset of N-1 elements. Following our pattern, we can pick any N-1 of those elements to go first in that subset. If we keep going, we end up with N-2, N-3, etc–all the way down to 1. When we reach a set of 1 element, we’re done. This is our base case.

The trickiest part is knowing how to combine these results.

Starting with N elements, we have N choices for the first one. For each of those N choices, we have N-1 sub-choices. These are multiplied together to give us the total number of choices, N * (N-1). But we aren’t done, because have to consider the N-2 choices for each of the N-1 sub-choices, for each of the N original choices, which is N * (N-1) * (N-2). If you continue this pattern all the way down to 1, you get the familiar factorial function, N! Going back to our example, we had 3 choices for our first element, which gave us the three lines above. For each of those 3 lines, we had a 2 element subset, of which the permutations are merely the 2 possible “flippings” of those elements. We ended up with 3*2*1 = 6 permutations, just as we expected.

Thus, the answer to our question, “how many permutations are there of a set?” is N!, where N is the number of elements in our set.

Combinations

You may be familiar with the “n choose r” notation, which is denoted mathematically by the following equation:

\binom{n}{r} = \frac{n!}{r!(n-r)!}

This is a pretty scary looking equation, and it’s not easy to “reverse engineer.” the meaning by just looking at it. Fortunately, there’s an easy way to understand it that builds on the idea of permutations presented in the previous section, so bear with me.

First of all, what is a combination? Remember how permutations were ordered sets? The key behind a combination is that it is unordered. How many ways can you divide a group of 4 students into 2 person teams? That’s a combination problem. We don’t care who’s first or second on each team–only who is on each team. Thinking about it, combinations must somehow relate to permutations. More precisely, the combinations must be a subset of the permutations. Why? Well, if you have any combination of students on a team, you could generate permutations from that–by picking someone to go first, etc., like we learned above. It “feels” like there are duplicate sets being counted that we don’t care about–which is exactly the case. The equation above is basically computing all possible permutations and then “trimming” the duplicate results to give us the combinations.

With that insight, let’s examine that scary equation once again, just for a bit.

\binom{n}{r} = \frac{n!}{r!(n-r)!}

This equation is saying, “how many ways can we choose r elements from n elements?” Using our team example above, we’d be choosing 2 person teams from 4 total people. Let’s plug it in and see what we get:

\binom{4}{2} = \frac{4!}{2!(4-2)!} = \frac{24}{2*2} = 6

Given a set, \left \{abcd \right \}, it’s not too hard to pick out those 6 combinations:

\left \{ab\right \} \left \{ac \right \} \left \{ad \right \} \left \{bc \right \} \left \{bd \right \} \left \{cd \right \}

As you can see, each combination includes a unique group of people, in no particular order. We could visit each of these groups, permute them by picking all possible orderings, and combine the results to get 24 total permutations. I’ll leave that as an exercise for you. The key insight is that we can compute permutations from combinations. Each permutation is the same combination, just mixed up differently. Let’s just examine one of these combinations: \left \{ab\right \}.

Finding the permutations in this set is trivial. Here they are:

\left \{ab \right \} \left \{ba \right \}

There are 2! = 2 permutations here. These are the permutations of the combination, \left \{ab\right \}. Hmmm, it seems like we’re ending up with twice as many results as we want. For each combination, we have a duplicate. We need to take our original n! permutation estimate and somehow remove these duplicates. We do this by dividing by r!. Think about it, if we have a 2 element set, we end up double counting everything. We need to divide by 2. If we had a 3 element set, we could have even more duplicates. We would need to divide by 3! = 6.

Using our previous example, dividing 24 (the number of permutations of n elements) by 2 (the number of permutations of r elements) gives us 12–not 6. What gives?

We’ve still got the (n – r)! term in there. If you think about it, n-r counts the remaining elements not chosen in our combination. Let’s take a look at our team example once more to see why we need this.

Let’s say we’ve chosen the combination, \left \{ab \right \}. We know that this expands into 2 permutations, so we divide our total number of permutations (24 in this example) by 2, but we still have duplicates. The issue is that our n! permutations still include permutations of the remaining elements, which are incorrectly included in our count. Let’s examine our first combination once again:

\left \{ab \right \}

We know we can permute this, but we still have to combine it with the remaining unused elements, which combined form a permutation of the original set. Thus, even if we purge duplicates from our subset, we still end up with more duplicates. Assuming we’ve purged duplicates from our example subset, our combined set still includes the permuted unused elements:

\left \{abcd \right \} \left \{abdc \right \}

To correct this, we need to divide by the (n-r) element permutations, which gives us the missing (n-r)! term. If we divide our original n! permutations by these two terms, we finally get the correct result:

\binom{n}{r} = \frac{n!}{r!(n-r)!}

Simulating an Inverse Kinematics Chain

Inverse kinematics is a fun application of linear algebra and calculus that is extremely relevant in computer animation. Given a rigged skeleton, inverse kinematics can solve the joint angles (or similar parameters for other types of joints) necessary to minimize the distance between the end effector (i.e. joint at the end of the chain) and target. Solving this system essentially boils down to the following system of equations:

\vec{e}=J\vec{\Delta\theta}

where \vec{e} is called the “error vector,” and describes the velocity of the end effector necessary to converge on the target; \Delta\vec{\theta} is the vector of joint angle velocities that will result in the correct end effector velocity (this is the unknown part), and the Jacobian matrix J, that encodes the change of basis from joint angle space to Cartesian coordinate space for the partial derivatives. Alternatively, you can view this as a transformation matrix that takes the rate of change of the joint angles and relates it to the rate of change of the Cartesian coordinates of the end effector joint.

It is common to have more columns than rows in a system like this (especially in a chain), because the there will be few end effectors and many joints. Because the matrix is not invertible, our next best thing is the Moore-Penrose psuedoinverse which gives a least-squares solution to the problem. This is desirable because there are many cases where the chain cannot converge on the target, so we want the best possible attempt. The results in the following equation:

\Delta\vec{\theta}=J^T(JJ^T)^{-1}\vec{e}

This form of the psuedoinverse assumes that you have full row rank in your matrix J, otherwise JJ^T will be singular an non-invertible. This presents a problem because there do exist singularities in certain joint configurations. A common solution to this problem is to damp this matrix by a small factor to ensure invertibility. This method is called the Damped Least Squares method, and the requires only a simple change to the previous equation:

\Delta\vec{\theta}=J^T(JJ^T + \lambda I)^{-1}\vec{e}

Here, \lambda is just an arbitrarily chosen constant that keeps the matrix from every going singular. The bigger the constant, the less realistic the motion near singular configurations. On the other hand, a higher constant results in more numerical stability in the equations. The demo I wrote allows you to set an arbitrary \lambda value.

I also implemented two other solvers, a Jacobian Transpose solver and a Cyclic-Coordinate Decent solver. The former cheats by using the transpose of the Jacobian to solve the system rather than the psuedoinverse. It’s a simple solution but results in a lot of jittery motion and isn’t very realistic. CCD essentially loops through each joint multiple times and orients the child chain in the direction of the target. With enough iterations, this converges on a solution, but it only works in situations where joints are 1DOF. It is quite simple to understand and there are several articles online that explain it well.

Finally, the demo is written in Python using the pyglet library. User interactions is almost exclusively through a console interface (activated with ~). Included in the zip is a text file with the syntax for these commands.

Source Archive

For a more in-depth introduction to this topic, I found this paper extremely helpful.

Build a strong math foundation!

A strong math background is an vital tool for game development. That may sound completely obvious to you, but it wasn’t to the 12-18 year old me. I was a good student and enjoyed my math classes and all, but the light just wasn’t on. I never took a formal linear algebra class, so the best I had was the primer you get in every game development book. It’s enough to understand basic vector algebra and affine transformations, but not much more. I mostly just used the equations and maintained a very surface-level understanding. The dangerous part was that I somehow fostered a false confidence in my math skills. I was good until I started prodding.

Man, was I missing out.

Last year, I had the opportunity to interview for a game development studio. Sure enough, my interviewer gave me a vector algebra problem, and I totally choked. I eventually made it through, but not without lots of coaxing and hand holding. It was a pivotal moment for me: I realized just how much I was holding myself back by not building a strong foundation. So I decided to change!

I immediately picked up Introduction to Linear Algebra by Gilbert Strang and began working through his M.I.T. course online. I also registered for Calculus III for Fall 2012, and Differential Equations, and Computational Geometry for my last semester. I picked up Real-Time Rendering and Physically Based Rendering, which are two fantastic and math-heavy books. Linear algebra and Calculus III have been incredible. I’m able to dissect problems and understand their context in ways like never before.

As an example, consider the problem of tangent space normal mapping. I never understood the formal concept of linear transformations and basis vectors. A matrix was just numbers to me; now it’s a familiar construct with a plethora of fascinating properties and elements (like eigenvalues and eigenvectors!). Computing the tangent, bi-tangent, and normal vectors and transforming the lights  and viewpoint into tangent space is a walk in the park now. No game development book primer is a worthy replacement for a rigorous math course.

So do yourself a favor. Learn the math! And really learn it.

Most recently, I’ve been studying the Singular Value Decomposition of a matrix, as well as it’s Psuedoinverse. These constructs are ways to break down matrices into basic and powerful elements. A great application of this concept is inverse kinematics. In my next post, I’ll explain how I solved a basic inverse kinematics chain in 2D using python, linear algebra, and calculus.