Want to take part in these discussions? Sign in if you have an account, or apply for one below
Vanilla 1.1.10 is a product of Lussumo. More Information: Documentation, Community Support.
Is there a way that makes finding inverses a bit easier?
I defined a really nice pairing function based on a space filling curve which acts on natural numbers,
,
and would like to find it’s projections. Is such a thing possible?
This seems to work, i.e., gives a bijection , although it’s a tad unusual. (I wouldn’t call it a “space-filling curve” though; in usual parlance, a space-filling curve is a continuous surjection with domain the unit interval , e.g., .) Also, it’s much more common to use a simpler-looking one-line formula such as
But anyway, if labels the grid point , and if denotes the floor function, then putting we have
assuming my calculations are correct (which I won’t swear to).
Oh, by the way, notice that , so your third and fourth lines could have been combined into a single line.
Thank you, Todd.
Actually, here’s an even better function I figured out that’s based on the curve I wanted that I was trying to define last night:
I could see it being a mechanical way to iterate an infinite matrix, so having the projections has an actual real world use.
Edit: I made it from chopping in half, then flipping the pairing function:
Again, it should not be called a “space-filling curve”.
I’m mildly curious why this choice of bijection in 3., with the bifurcation into odd and even cases. A cousin to the bijection of 1. is the two-line expression
which to me looks simpler, and is closely connected with a standard well-ordering on where if either or or . (A similar type of well-ordering arises in one of the standard proofs that for infinite cardinals , assuming the axiom of choice.)
That I can answer quite easily, The reason for splitting the terms into odd and even case can be seen from the tables:
Compare the image of,
Image: http://imgur.com/KsskDoQ
with that of,
Image: http://imgur.com/NIok3JM
Also, from Cantor’s pairng function,
Image: http://imgur.com/Nh25uoj
I found the derivation,
Image: http://imgur.com/CXmfFAE
Splitting up the functions this way allows for “ox-plowing” variants.
I was motivated by the page http://mathworld.wolfram.com/PairingFunction.html, which pointed out that the two ox-plowing functions given by Stein in his book had no explicit formula. Well, now they do.
As a bonus, here’s the pairing function I first defined,
Image: http://imgur.com/as34fVe
While this is nice to think about, is there are reason why the question was asked here rather than, for example, math.stackexchange?
1 to 6 of 6