Say you have an array whose length is a power of some base b. For most of this post we’ll be using powers of two, but we’ll discuss other bases as well. Imagine that there is a b-ary tree over the array. We want to shuffle the array in the following way: randomly shuffle the b sub-trees of the root. Then, recurse into each subtree, and do the same, until we get to the bottom.

That subtitle is a little bit of a mouthful, but I’ve been wanting to talk about Andrew Kensler’s permute() function for a while and I wanted to make it clear right off the bat why it’s useful. permute() is used some in the graphics community, especially in offline rendering, and the techniques are more widely known in cryptography*, but it’s applicable to so much more than graphics and cryptography.