Pairing functions are fun. Last week, we had a look at the Cantor/Hopcroft and Ullman function, and this week, we’ll have a look at the Rosenberg-Strong function—and we’ll modify it a bit.

The Rosenberg-Strong function [1,2] maps the pairs (i,j) in the following way:

If we look at it closely, we see that numbers aren’t placed on diagonals, but in “shells” (technically, gnomons). The original idea was to use this as a storage allocation method, so that each new “shell” was somehow minimal (I am not convinced how this is meant to make sense in block-based storage).

How do we construct the function? Well, first thing is to figure how to generate the shells:

That’s easily found: the shell number is simply max(i,j)! We then notice a pattern linking the number of the shell and its first number:

Now to compute the numbers in the gnomon, let’s assume i are rows and j columns. If i is equal to the row, we add j; if j is equal to the column, we add i, plus the middle of the interval. This is j+max(i,j)-i. The inverse is almost simpler than the function itself.

To find the inverse, we notice that the shell containing some number is . Then is the base of the shell; is the “rest” the position of on the gnomon; if (the gnomon with base has numbers on it), it's on the horizontal section and the pair is , otherwise it's on the vertical part, and the pair is $(2b-r,b)$.

The Mathematica code is:

s[i_, j_] := Max[i, j]^2 + j + (Max[i, j] - i) is[n_] := Module[{b = Floor[Sqrt[n]], r}, r = n - b^2; If[r < b, {b, r}, {2 b - r, b} ] ]

*

* *

The scan order imposed by the Rosenberg-Strong function is:

We see that at each gnomon’s end, we jump across the map to the other side. What we could want, is rather that it wraps always to a close neighbor.

Fortunately, getting a boustrophedonic variant isn’t hard at all! If the shell is even, we wind it one way; if it’s odd, we wind it the other:

We, indeed, get:

The Mathematica code is:

bs[i_, j_] := If[EvenQ[Max[i, j]^2], s[i, j], s[j, i]] ibs[n_] := Module[{t = is[n]}, If[EvenQ[Max[t]^2], t, Reverse[t]] ]

*

* *

What if we’re interested in more than two numbers? We could, of course, devise some complicated function for 3, or more; but we can use the following relations to accomplish just that with function :

,

,

,

etc.

[1] Arnold L. Rosenberg — *Allocating Storage for Extendible Arrays* — J. ACM, vol 21, no 4 (1974), p. 652–670

[2] Arnold L. Rosenberg, H. R. Strong — *Addressing Arrays by Shells* — IBM Technical Disclosure Bulletin, vol 14, no 10 (1972), p. 3026–3028

[…] [1] Steven Pigeon, Mœud , Mœud deux [2] Wikipedia, Pairing function [3] OEIS, A319571 , A319514 [4] The Julia programming […]

Thank you, I enjoyed your blogs post very much. I implemented the proposed algorithms as state machines in the Julia language and uploaded the enumerations as sequences to the OEIS. You find the links on my blog: https://wp.me/paipV7-d

Thanks!