Show HN: The King Wen Permutation: [52, 10, 2] (gzw1987-bit.github.io)

Well... you could describe it that way, if you wanted to.

The Wolfenstein 3D code implements a function from a coordinate pair (x₁, y₁) to a new coordinate pair (x₂, y₂) which has the property that, if you start with the pair (0, 1), repeatedly applying the function will take you through every coordinate pair that represents a valid pixel on screen and then return to (0, 1).

"Cycle" in the context of permutations still refers to the process of applying a function repeatedly and ultimately returning to the original value you started with, but there is no concept of "visiting every valid value in between".

(And this is not a necessary part of the phenomenon in Wolfenstein, either; it could, theoretically, have used a function that painted three different points red and never visited the rest of the screen. "Cycle" directly refers to the fact that repeated application of the function will eventually produce a result that has been seen before, which Wolfenstein uses as the condition to break out of a while loop. The fact that every pixel on screen has been visited at that point is a fact about the "cycle length".)

I wrote up something of a description of permutation cycles before looking up the Wolfenstein thing, so here it is:

---

Permutations are usually considered in terms of the "cycles" that make them up.

Intuitively, you can describe a permutation by explicitly listing the position to which it assigns everything. In this method,

    [1, 4, 2, 5, 3]

is a permutation of 5 objects which places the first object first, the second object third, the third object fifth, the fourth object second, and the fifth object fourth.

This is cumbersome, and it obscures the internal structure of the permutation. It is more conventional to describe a permutation as a collection of cycles; our example permutation would be given as

    (1)(2 4 5 3)

This tells us that the first element is in a 1-length cycle with itself, and the other four elements share a 4-length cycle. Specifically, after one application of the permutation, element 4 will conceptually metamorphose into element 5 (which follows "4" in the cycle), element 2 will become element 4, element 3 will become element 2, element 1 will stay right where it is, and so forth.

This representation, among other virtues, makes it pretty easy to compute the order of the elements after one, or more, applications:

     (0) [1, 2, 3, 4, 5]
     (1) [1, 4, 2, 5, 3]
     (2) [1, 5, 4, 3, 2]
     (3) [1, 3, 5, 2, 4]
     (4) [1, 2, 3, 4, 5]

After four applications, we've come back to the original order of the elements. This is because our permutation contains a 1-cycle and a 4-cycle, and the least common multiple of 1 and 4 (the cycle lengths) is 4 (the number of applications required to return to the original order). You can see the 1-cycle running down the column at position 1, and you can see the 4-cycle running down the columns at positions 2, 4, 5, and 3, which are the elements contained in that cycle.

Armed with this, we can go a little further: after 75 applications, 1 will advance through its cycle 75 times (remaining "1"), and each other position will advance through its cycle 75 times. Since that cycle is 4 elements long, this is the same as advancing 75 mod 4 (= 3) times, giving us

    (75) [1, 3, 5, 2, 4]

It turns out that every permutation arranges elements into cycles like this. We could consider a permutation on two objects:

    (1 2)

which swaps the objects. We can consider what is essentially the same permutation on 200 objects:

    (1 2)

which swaps the first two objects while leaving the other 198 objects in place. (Formally, those objects are all in 1-cycles, and we just don't bother writing them all down.) With a slightly more complex permutation on 200 objects:

    (3 70 54 159)
<...