Why You Should Get A Coding Cap June 5th, 2009
Patrick Stein

Way back when I was at Computer Science House I discovered coding caps. We were working on a Virtual Reality project (I told you it was way back, right?). While we were working, a company called Virtuality made a stop at R.I.T. as part of a larger tour of campuses showing off their VR game.

Guess Jeans was one of the sponsors of their tour. All of us working on the VR project ended up with black baseball-ish caps that said Guess across the front. We wore those caps all of the time we were coding.

Lately, I’ve been having trouble focusing on coding when I am gifted with some moments to spare. I thought, How about I get a coding cap? I tried this about a year ago when I was having similar trouble. The cap didn’t really work then. The cap would itch after a few hours, and before that, I would forget I was wearing it. Once you start reading email and answering the phone in your coding cap, it loses its power.

So, today, I set out looking for a new coding cap… one that I could wear for a few hours, but one that I would notice I was wearing. I tried on a few hats. None of them felt powerful enough. They didn’t have the coding cap magic.

I grabbed a pair of lace-up, fishnet, fingerless gloves. I plan to leave one by my keyboard and the other in my purse. When it’s coding time, I’ll slip one on.

So far, they seem to work. When I reach to check email, I immediately notice my glove and stop. When the phone rings, I peek at the caller-id and decide whether it’s worth it to remove the glove. Sorry, Out of Area: I’m coding right now, and I don’t want to have to take off my glove to hear about the great things you can do for my windshield/interest-rates/auto-warranty/credit-card-processing.

Do you have a coding cap? specific lighting? specific music?

Installing mpich2 for use with CL-MPI June 5th, 2009
Patrick Stein

Some time back, I began writing some OpenMPI wrappers for Lisp. I got everything that I needed working, but I hardly scratched the surface of what MPI-2 makes available.

Recently, Alex Fukunaga started up a blog about Lisp. One of the things he has done is make CFFI bindings for mpich2. Here is an introductory post about those bindings with a link to his CL-MPI site.

Today, I have been working on getting his bindings up and running under Ubuntu Linux and Mac OS X.

Read the rest of this entry ⇒

Study with Me — Maybe Relation Algebras? June 4th, 2009
Patrick Stein

In an earlier post, I was soliciting recommendations for texts to study since I cannot seem to get Cambridge University Press to respond to me. Paul Reiners suggested (amongst other things) Relation Algebras by Games by Hirsch and Hodkinson.

I went to the Math Library at the U of MN yesterday to look through it. I only had a quick glance since I had my 11-month-old in tow. As I am no longer staff or student at the U, I could not check it out. However, as I have a Hennepin County Library card, I am able to request it via Interlibrary Loan. Soon, I will have a chance to assess it more carefully.

A Recurrence of Constrained Shuffles June 2nd, 2009
Patrick Stein

Earlier, I posted about finding the Fibonacci numbers when counting a very simple constrained shuffle. In that article, I was concerned with the question: How many permutations are there in \Sigma_n such that \left| \pi(i) - i \right| \le 1 for all i \in [1,n]?

For that problem, the answer was F_{n+1}. The number of permutations on n items where no item moves more than one space from where it started is the (n+1)-th Fibonacci number. Now, the obvious question is: How many permutations are there in \Sigma_n such that \left| \pi(i) - i \right| \le k for i \in [1,n] and k is an arbitrary positive integer?

Let’s not start so arbitrary just yet though…

Let’s just look for a moment at how much trickier things become when we let k = 2. It’s easy enough for n = 1. There’s only one shuffle possible and it satisfies the constraint. For that matter, the same is (conventionally) true for n = 0. When you have zero items, there is only one (very Zen) way to shuffle them, and it certainly does not violate the constraints.

For n = 2, there are two shuffles. Both satisfy the constraints. Similarly, with n = 3, there are 3! = 6 shuffles. All of them satisfy the constraints.

For n = 4, we get to the first interesting case. Here, some of the 4! = 24 shuffles violate the constraints. So, how many shuffles are still possible? To tackle this, we are going to use an inclusion-exclusion counting. The only items that could be out of place are the first and the last. So, how many of the 4! shuffles have either the first element move to the back or the last element move to the front?

There are 3! permutations that send the first element to the back. There are 3! permutations that send the last element to the front. We might then think that there are 4! - 2\cdot 3! valid shuffles. Alas, there are some shuffles that move both the first element to the back and the last element to the front. We have counted those twice. There are 2! = 2 of those.

So, for n = 4, there are 4! - 2\cdot 3! + 2! = 24 - 12 + 2 = 14 shuffles satisfying our constraint that \left| \pi(i) - i \right| \le 2.

What then of n = 5? Well, it’s bedtime here. This is gonna have to wait.

Goodnight.

Google Is Fast May 31st, 2009
Patrick Stein

A few hours after posting about constrained shuffles and the Fibonacci numbers, I decided to search for papers on constrained shuffles. Google had already indexed my article. I came up second. I like.

It may be they monitor pingomatic. Or, it may be because I have Google ads on the page. Either way, it feels oddly powerful to be able to type and be recorded.

Umm… now if only some other people searched for constrained shuffles. 😉

Updates In Email

Email:

RSS Feeds

l