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<b (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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: