Mœud deux

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 $n$ is $b=\lfloor \sqrt{n} \rfloor$. Then $b^2$ is the base of the shell; $r=n-b^2$ is the “rest” the position of $n$ on the gnomon; if $r (the gnomon with base $b$ has $2b+1$ numbers on it), it's on the horizontal section and the pair is $(b,r)$, 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:

$s'_{ij}=\begin{cases} s_{ij}&\mathrm{if~}\max(i,j)\mathrm{~is~even}\\ s_{ji}&\mathrm{otherwise}. \end{cases}$

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 $F$:

$F(i,j,k)=F(i,F(j,k))$,

$F(i,j,k,l)=F(F(i,j),F(k,l))$,

$F(i,j,k,l,m)=F(i,F(F(j,k),F(l,m)))$,

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

3 Responses to Mœud deux

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

2. luschny says:

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