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.

I Discovered The Fibonacci Numbers May 31st, 2009
Patrick Stein

Alright, I wasn’t the first. But, I wasn’t particularly expecting to find them either.

One nascent game concept that I have in my head requires me to do some constrained shuffling. As an example constraint, imagine that you need to shuffle a deck of cards while ensuring that no card moved more than five spots away from where it started. Or, imagine that you had to shuffle the deck so that a card of rank r could only move to spot that had been held by a card of rank r-1, r, or r+1.

In the general case, you have a directed graph with vertexes \left\{ v_1, v_2, v_3, \ldots, v_n \right\} and a permutation \pi such that \pi(i) can only equal j if there is an edge in the graph from v_i to v_j.

Well, as this is for a game, it would get pretty boring if there were only a few possible shuffles. On the other hand, if there are a large number of possible shuffles, then I haven’t really restricted the shuffling at all for all practical purposes. So, then the question is: for a given directed graph, how many possible shuffles are there? Can I generate them without generating any of the invalid permutations, too?

Today, I started with the How many?-question. I started with a very simple graph. The vertexes are spaced evenly along an east-west line. Each vertex is connected only to itself, its nearest neighbor to the east, and its nearest neighbor to the west. Put another way, \left| \pi(i) - i \right| \le 1 for i \in [1,n].

Let’s say we already had a row of n-1 vertexes. If we add another vertex at the beginning of the row, then there are two things that a shuffle can do to that new vertex: leave it where it is or swap it with what had been the first vertex in the row. Now, suppose that c(n) is the count of valid shuffles for n vertexes in this configuration. The case where our new vertex stays where it is leaves c(n-1) possibilities for the rest of the row. The case where our new vertex swaps places with the old first vertex leaves c(n-2) possibilities. As such, c(n) = c(n-1) + c(n-2).

Cha-ching. Note that c(1) = 1 and c(2) = 2, then c(n) = F_{n+1} where F_i are the Fibonacci numbers.

Things get a great deal messier if we move up to \left| \pi(i) - i \right| \le 2. More on that some other time…

How to Make a Weighted Random Choice May 5th, 2009
Patrick Stein

Today seemed like a dull day at the keyboard. I beat my head against Objective C a lot. And, I implemented a weighted random choice which I have done a thousand times before. Dull, right?

I needed a weighted random choice in two different places, and I implemented it differently in each place. Weird, right? Even weirder, I think I did the right thing in each place.

Picking a card from a deck

In the first case, I needed to choose a flash card from a deck. I want to favor cards that have given the player trouble in the past. I zip through the list once to sum up the weights. Then, I pick a random number greater or equal to zero and less than the sum of the weights. Then, I run through the list again summing the weights until my running sum exceeds my random number. (Here in Perl, um, for clarity?):

my $total = 0.0;
foreach my $item ( @list_of_items ) {
    $total += weight( $item );
}

my $thresh = rand( $total );
my $found;

foreach my $item ( @list_of_items ) {
    $thresh -= weight( $item );
    if ( $thresh < 0.0 ) {
        $found = $item;
        last;
    }
}

This requires that the weight() of a given item remains constant for the duration of the function. The weight() can change between choices, however. If the weight() will remain constant for large portions of the program then you can cache the total and only bother with the second half of the loop.

Choosing a letter of the alphabet

In a different portion of the program, I need to make random letter tiles. I feel like there should be more E‘s than Q‘s. I also want to leave a pathway to use the same artwork for different languages. Because of all of this, I opted to have the weights to come in from a file.

My data file is JSON encoded. I could, I suppose, do something like this (given the English letter frequencies):

{
    "english" : {
        "A": 8.167,
        "B": 1.492,
        "C": 2.782,
        ...
    }
}

But, that hurts to even think about. Instead, I opted to round them off to integer proportions. Then, I could just do this:

{
    "english": "AAAAAAAABBCCC..."
}

Now, making a random choice simply involves selecting one character from the string.

Exponential Spirals for Game Effects May 4th, 2009
Patrick Stein

In earlier posts, I mentioned finding polynomials, riffing off of damped harmonic motion, and then hitting on exponential spirals all trying to come up with a nice looking way to snap game tiles back into place when they are released. I want them to overshoot and then settle into place rather than snap directly into their spot.

The Basic Spiral

I am talking about a simple spiral of the form:

\theta(t) = Kt
r(t) = \alpha\left(Kt\right)^{n}
for some integer n.

That would be an equation for a spiral that starts at the origin and heads outward as t increases. For my application though, I want to end at the origin so I need to substitute 1-t in for t.

\theta(t) = K(1-t)
r(t) = \alpha\left(K(1-t)\right)^{n}

The math is also going to work out slightly better if I use n-2 in place of n in the above equations:

\theta(t) = K(1-t)
r(t) = \alpha\left(K(1-t)\right)^{n-2}

I don’t want the piece to spiral into place when released though. So, really, I am concerned with just the x coordinate from the above equations:

x(t) = r(t) \cos \theta(t) = \alpha K^{n-2} (1-t)^{n-2} \cos \left(K\left(1-t\right)\right)

To normalize everything, I am going to let \alpha = K^{2-n}. And, since I want my interpolation value to go from zero to one instead of one to zero, I am again going to subtract this all from one:

x(t) = 1 - (1-t)^{n-2} \cos \left(K\left(1-t\right)\right)

Read the rest of this entry ⇒

A Eureka Moment May 1st, 2009
Patrick Stein

I was pondering the Phony Physics again as I set to work on my iPhone app.

In the previous post, I twiddled the equations for damped spring motion until I found something visually pleasing. Last night, I went back to the drawing (a.k.a. white) board.

What if I used an exponential spiral (parameterized by arc length). Then, I could easily adjust the number of times it bounces back and forth. I could use a spiral like r(t) = \alpha K (1-t)^n and \theta(t) = K(1-t) where K is some multiple of 2\pi. Then, I could walk along the spiral getting to the origin when t = 1 going around the origin \frac{K}{2\pi} times in the process. If I follow the curve at a fixed rate, then I guarantee that my oscillations will pick up speed as I approach the origin.

Rather than have it spiral into the center, I am just using the x-coordinate of the spiral as my new t value to interpolate with. I like the effect for the most part. It overshoots a little bit far on the first oscillation. I may tweak it some more before it’s all over. For now though, I am sticking with it.

I will post some graphs soon.

Updates In Email

Email:

RSS Feeds

l