2026-01-02 04:48:02
The previous post talked about doing perfect shuffles: divide a deck in half, and alternately let one card from each half fall.
It matters which half lets a card fall first. If the top half’s bottom card falls first, this is called an in-shuffle. If the bottom half’s bottom card falls first, it’s called an out-shuffle.
With an out-shuffle, the top and bottom cards don’t move. Presumably it’s called an out-shuffle because the outside cards remain in place.
An out-shuffle amounts to an in-shuffle of the inner cards, i.e. the rest of the deck not including the top and bottom card.
The previous post had a Python function for doing an in-shuffle. Here we generalize the function to do either an in-shuffle or an out-shuffle. We also get rid of the list comprehension, making the code longer but easier to understand.
def shuffle2(deck, inside = True):
n = len(deck)
top = deck[: n//2]
bottom = deck[n//2 :]
if inside:
first, second = bottom, top
else:
first, second = top, bottom
newdeck = []
for p in zip(first, second):
newdeck.extend(p)
return newdeck
Let’s use this code to demonstrate that an out-shuffle amounts to an in-shuffle of the inner cards.
deck = list(range(10)) d1 = shuffle2(deck, False) d2 = [deck[0]] + shuffle2(deck[1:9], True) + [deck[9]] print(d1) print(d2)
Both print statements produce [0, 5, 1, 6, 2, 7, 3, 8, 4, 9].
I said in the previous post that k perfect in-shuffles will restore the order of a deck of n cards if
2k = 1 (mod n + 1).
It follows that k perfect out-shuffles will restore the order of a deck of n cards if
2k = 1 (mod n − 1)
since an out-shuffle of n cards is essentially an in-shuffle of the n − 2 cards in the middle.
So, for example, it only takes 8 out-shuffles to return a deck of 52 cards to its original order.
The post In-shuffles and out-shuffles first appeared on John D. Cook.2026-01-01 21:31:18
Take a deck of cards and cut it in half, placing the top half of the deck in one hand and the bottom half in the other. Now bend the stack of cards in each hand and let cards alternately fall from each hand. This is called a rifle shuffle.
Persi Diaconis proved that it takes seven shuffles to fully randomize a desk of 52 cards. He studied videos of people shuffling cards in order to construct a realistic model of the shuffling process.
Shuffling randomizes a deck of cards due to imperfections in the process. You may not cut the deck exactly in half, and you don’t exactly interleave the two halves of the deck. Maybe one card falls from your left hand, then two from your right, etc.
Diaconis modeled the process with a probability distribution on how many cards are likely to fall each time. And because his model was realistic, after seven shuffles a deck really is well randomized.
Now suppose we take the imperfection out of shuffling. We do cut the deck of cards exactly in half each time, and we let exactly one card fall from each half each time. And to be specific, let’s say the first card will always fall from the top half of the deck. That is, we do an in-shuffle. (See the next post for a discussion of in-shuffles and out-shuffles.) A perfect shuffle does not randomize a deck because it’s a deterministic permutation.
To illustrate a perfect in-shuffle, suppose you start with a deck of these six cards.
Then you divide the deck into two halves.
Then after the shuffle you have the following.
Incidentally, I created the images above using a font that included glyphs for the Unicode characters for playing cards. More on that here. The font produced black-and-white images, so I edited the output in GIMP to turn things red that should be red.
If you do enough perfect shuffles, the deck returns to its original order. This could be the basis for a magic trick, if the magician has the skill to repeatedly perform a perfect shuffle.
Performing k perfect in-shuffles will restore the order of a deck of n cards if
2k = 1 (mod n + 1).
So, for example, after 52 in-shuffles, a deck of 52 cards returns to its original order. We can see this from a quick calculation at the Python REPL:
>>> 2**52 % 53 1
With slightly more work we can show that less than 52 shuffles won’t do.
>>> for k in range(1, 53):
... if 2**k % 53 == 1: print(k)
52
The minimum number of shuffles is not always the same as the size of the deck. For example, it takes 4 shuffles to restore the order of a desk of 14 cards.
>>> 2**4 % 15 1
Here’s a function to perform a perfect in-shuffle.
def shuffle(deck):
n = len(deck)
return [item for pair in zip(deck[n//2 :], deck[:n//2]) for item in pair]
With this you can confirm the results above. For example,
n = 14
k = 4
deck = list(range(n))
for _ in range(k):
deck = shuffle(deck)
print(deck)
This prints 0, 1, 2, …, 13 as expected.
2025-12-31 21:48:24
Donald Knuth gives a public lecture each year around Christmas. This year was his 29th Christmas lecture, Adventures with Knight’s Tours.
I reproduced one of the images from his lecture.
This is the knight’s tour with the minimum number of obtuse angles, marked with red dots. The solution is unique, up to rotations and reflections.
Knuth said he thought this was one of the most beautiful knight’s tours. He discusses this tour about 44 minutes into the video here.
2025-12-29 19:00:48
If the earth were a perfect sphere, “down” would be the direction to the center of the earth, wherever you stand. But because our planet is a bit flattened at the poles, a line perpendicular to the surface and a line to the center of the earth are not the same. They’re nearly the same because the earth is nearly a sphere, but not exactly, unless you’re at the equator or at one of the poles. Sometimes the difference matters and sometimes it does not.
From a given point on the earth’s surface, draw two lines: one straight down (i.e. perpendicular to the surface) and one straight to the center of the earth. The angle φ that the former makes with the equatorial plane is geographic latitude. The angle θ that the latter makes with the equatorial plane is geocentric latitude.
For illustration we will draw an ellipse that is far more eccentric than a polar cross-section of the earth.
At first it may not be clear why geographic latitude is defined the way it is; geocentric latitude is conceptually simpler. But geographic latitude is easier to measure: a plumb bob will show you which direction is straight down.
There may be some slight variation between the direction of a plumb bob and a perpendicular to the earth’s surface due to variations in surface gravity. However, the deviations due to gravity are a couple orders of magnitude smaller than the differences between geographic and geocentric latitude.
The conversion between the two latitudes is as follows.
Here e is eccentricity. The equations above work for any ellipsoid, but for earth in particular e² = 0.00669438.
The function atan2(y, x) returns an angle in the same quadrant as the point (x, y) whose tangent is y/x. [1]
As a quick sanity check on the equations, note that when eccentricity e is zero, i.e. in the case of a circle, φ = θ. Also, if φ = 0 then θ = φ for all eccentricity values.
Next we give a proof of the equations above.
We can parameterize an ellipse with semi-major axis a and semi-minor axis b by
The slope at a point (x(t), y(t)) is the ratio
and so the slope of a line perpendicular to the tangent, i.e tan φ, is
Now
and so
where e² = 1 − b²/a² is the eccentricity of the ellipse. Therefore
and the equations at the top of the post follow.
For the earth’s shape, e² = 0.006694 per WGS84. For small eccentricities, the difference between geographic and geocentric latitude is approximately symmetric around 45°.
But for larger values of eccentricity the asymmetry becomes more pronounced.
[1] There are a couple complications with programming language implementations of atan2. Some call the function arctan2 and some reverse the order of the arguments. More on that here.
The post The center of the earth is not straight down first appeared on John D. Cook.2025-12-29 09:23:19
One of the things I found off-putting about category theory when I was first exposed to it was its reliance on the notion of “collections” that are not sets. That seemed to place the entire theory on dubious foundations with paradoxes looming around every corner.
It turns out you can mostly ignore such issues in application. You can, for example, talk about the forgetful functor that maps a group to the set of its elements, ignoring the group structure, without having to think deeply about the collection of all sets, which Russell’s paradox tells us cannot itself be a set.
And yet issues of cardinality are not entirely avoidable. There is a theorem [1] that says in effect that category theory would be uninteresting without collections too large to be sets.
Every category C with a set of arrows is isomorphic to one in which the objects are sets and the arrows are functions.
If the collection of arrows (morphisms) between objects in C is so small as to be a set, then C is a sub-category of the category of sets. As Awodey explains, “the only special properties such categories can possess are ones that are categorically irrelevant, such as features of the objects that do not affect the arrows in any way.”
Most categories of interest have too many objects to be a set, and even more morphisms than objects.
[1] Category Theory by Steve Awodey. Theorem 1.6.
The post Interesting categories are big first appeared on John D. Cook.2025-12-27 19:14:04
One of my daughters gave me a Klein bottle for Christmas.
Imagine starting with a cylinder and joining the two ends together. This makes a torus (doughnut). But if you twist the ends before joining them, much like you twist the ends of a rectangular strip to make a Möbius strip, you get a Klein bottle. This isn’t possible to do in 3D without making the cylinder pass through itself, so you’re supposed to imagine that the part where the bottle intersects itself isn’t there.
But is a Klein bottle real? My Christmas present is a real physical object, so it’s real in that sense. Is a Klein bottle real as a mathematical object? Can it be defined without any appeal to imagining things that aren’t true? Yes it can.
Start with a unit square, the set of points (x, y) with 0 ≤ x, y ≤ 1. If you identify the top and bottom of the square, the points with y coordinate equal to 0 or 1, you get a cylinder. You can imagine curling the square in 3D and taping the top and bottom together.
Similarly, if you start with the unit square and identify the vertical sides together with a twist, you get a Möbius strip. You won’t be able to physically do this with a square, but you could with a rectangle. Or you could imagine the square to be made out of rubber, and you stretch it before you twist it and join the edges together.
If you start with the unit square and do both things described above—join the top and bottom as-is and join the sides with a twist—you get a Klein bottle. You can’t quite physically do both at the same time in 3D; you’d have to cut a little hole in the square to let part of the square pass through, as in the glass bottle at the top of the post.
Although you can’t construct a physical Klein bottle without a bit of cheating, there’s nothing wrong with the mathematical definition. There are some details that have been left out, but there’s nothing illegal about the construction.
To fill in the missing details, we have to say just what we mean by identifying points. When we identify the top edge and bottom edge of the square to make a cylinder, we mean that we imagine that for every x, (x, 0) and (x, 1) are the same point. Similarly, when we identify the sides with a twist, we imagine that for all y, (0, y) and (1, 1 − y) are the same point.
But this is unsatisfying. What does all this imagining mean? How is this any better than imagining that the hole in the glass bottle isn’t there? We can define what it means to “identify” or “glue” edges together in a way that’s perfectly rigorous.
We can say that as a set of points, the Klein bottle is
K = [0, 1) × [0, 1),
removing the top and right edge. But what makes this set of points a Klein bottle is the topology we put on it, the way we define which points are close together.
We define an ε neighborhood of a point (x, 0) to be the union of two half disks, the intersection with K of an open disk of radius ε centered at (x, 0) and the intersection with K of an open disk centered at (x, 1). This is a way to make rigorous the idea of gluing (x, 0) and (x, 1) together.
Along the same lines, we define an ε neighborhood of a point (0, y) to be the intersection with K of an open disk of radius ε centered at (0, y) and an open disk of radius ε centered at (1, 1 − y).
The discussion with coordinates is more complicated than the talk about imagining this and that, but it’s more rigorous. You can’t have simplicity and rigor at the same time, so you alternate back and forth. You think in terms of the simple visualization, but when you’re concerned that you may be saying something untrue, you go down to the detail of coordinates and prove things carefully.
Topology can seem all hand-wavy because that’s how topologist communicate. They speak in terms of twisting this and glueing that. But they have in the back of their mind that all these manipulations can be justified. The formalism may be left implicit, even in a scholarly publication, when it’s assumed that the reader could fill in the details. But when things are more subtle, the formalism is written out.
In the construction above, we define the Klein bottle as a set of points in the 2D plane with a new topology. That works, but there’s another approach. I said above that you can’t join the edges to make a Klein bottle in three dimensions. I added this disclaimer because you can join the edges without cheating if you work in higher dimensions.
If you’d like a parameterization of the Klein bottle, say because you want to calculate something, you can do that, but you’ll need to work in four dimensions. There’s more room to move around in higher dimensions, letting you do things you can’t do in three dimensions.
The post Klein bottle first appeared on John D. Cook.
