Symmetric injective mapping from N² to N

[Estanho]

Hi,

I've been trying to find one symmetric "injective" N²->N function, but could not find any. The quotes are there because the function I'm trying to find is not really injective, as I need that the two arguments be interchangeable and the value remains the same.
In other words, the tuple (a, b) yields the same result as (b, a), which defines simmetry, but the result of (a,b) and (b,a) should not be obtained by any other combination of arguments.

I'm also not sure how to prove if one such given function obeys this property, and this is one of the main problems, as I was able to find some that works for small numbers, but then fail with bigger ones (which makes it very hard for me to check).

If anyone could help me with this, it would be better if the output would not grow too fast.

Sorry if there any obvious candidates.

Thanks

 

[jbriggs444]

Not sure how obvious it is, but an easy first step would be to transform the original arguments (a,b) to a different pair (x,y) that contains all of the original information about (a,b) except for the question of which is greater than the other. This transformation is symmetric by design.

For instance:
(a,b) => (min(a,b), max(a,b)).
or
(a,b) => (|a-b|, a+b)

Now define your function from (x,y) into N.

 

[PeroK]

Hi,

I've been trying to find one symmetric "injective" N²->N function, but could not find any. The quotes are there because the function I'm trying to find is not really injective, as I need that the two arguments be interchangeable and the value remains the same.
In other words, the tuple (a, b) yields the same result as (b, a), which defines simmetry, but the result of (a,b) and (b,a) should not be obtained by any other combination of arguments.

I'm also not sure how to prove if one such given function obeys this property, and this is one of the main problems, as I was able to find some that works for small numbers, but then fail with bigger ones (which makes it very hard for me to check).

If anyone could help me with this, it would be better if the output would not grow too fast.

Sorry if there any obvious candidates.

Thanks

One idea is to map to a subset of N with integers composed of just the digits 1 and 2, for example.

 

[Estanho]

Not sure how obvious it is, but an easy first step would be to transform the original arguments (a,b) to a different pair (x,y) that contains all of the original information about (a,b) except for the question of which is greater than the other. This transformation is symmetric by design.

For instance:
(a,b) => (min(a,b), max(a,b)).
or
(a,b) => (|a-b|, a+b)

Now define your function from (x,y) into N.

That's an interesting one. I will try something on this.

One idea is to map to a subset of N with integers composed of just the digits 1 and 2, for example.

Well, that's a classical way to map infinite sets, but it breaks the need for the numbers to stay relatively small. In fact, any of mapping of this nature would grow very fast I think.
I'd like to be able to represent numbers up to the order of 50.000, but still be able to fit the correspondent number in a int64.

 

[PeroK]

That's an interesting one. I will try something on this.Well, that's a classical way to map infinite sets, but it breaks the need for the numbers to stay relatively small. In fact, any of mapping of this nature would grow very fast I think.
I'd like to be able to represent numbers up to the order of 50.000, but still be able to fit the correspondent number in a int64.

Well, you posted under Maths not computer science. Mapping a finite set is trivial.

 

[jbriggs444]

I'd like to be able to represent numbers up to the order of 50.000, but still be able to fit the correspondent number in a int64.

For efficient coding, you do not just want an injection. You want a bijection. Write down all the numbers from 0 up to the maximum positive integer you can support in a triangle pattern:

0
1  2
3  4  5
6  7  8  9
10 11 12 13 14
15 ...

The larger of your two inputs selects the row. The smaller selects the column. The formula for the first element in each row is well known.

That's an efficient use of [the positive half of] the code space. It may not be the most CPU-efficient coding scheme.

 

[Estanho]

Well, you posted under Maths not computer science. Mapping a finite set is trivial.

I see your point, and I appreciate your help. It's just that I will not be able to use a solution like this. I should have made it clear on the first post.
Also, I believe that the set of N² tuples and N are both infinite, but countable.

For efficient coding, you do not just want an injection. You want a bijection. Write down all the numbers from 0 up to the maximum positive integer you can support in a triangle pattern:

0
1  2
3  4  5
6  7  8  9
10 11 12 13 14
15 ...

The larger of your two inputs selects the row. The smaller selects the column. The formula for the first element in each row is well known.

That's an efficient use of [the positive half of] the code space. It may not be the most CPU-efficient coding scheme.

I can easily see that the formula for the first element of each row is given by the difference equation and boundary condition
<br /> x_n - x_{n-1} - n = 0,<br /> x_0 = 0<br />

which yields
<br /> x_n = \frac{n^2 + n}{2}<br />

As I understand, the column c will simply be summed with the value of the row, starting from 0. So, the final equation looks like:
<br /> x(r, c) = \frac{r^2 + r}{2} + c<br />
where r is greater than c. So, there's just the need to order the two arguments, by doing as your first tip, in this case (a, b) => (max(a,b), min(a,b))

Is that correct? It seems to map to your sketch (I'm lazy and haven't spread it any further, as it seems not to be necessary).

With this solution, as an int64 can go up to 9223372036854775807, we can find a good limit value for both r and c like this:
<br /> 9223372036854775807 = \frac{max^2 + max}{2} + max<br />
which yields max = 4294967295. This is much more than I expect to use.

If this is right, it is an excellent mapping in O(1).

 

[jbriggs444]

As I understand, the column c will simply be summed with the value of the row, starting from 0. So, the final equation looks like:

$x(r,c)=\frac{r^2+r}{2}+c$​

where r is greater than c. So, there's just the need to order the two arguments, by doing as your first tip, in this case (a, b) => (max(a,b), min(a,b))

Yep. That is what I had in mind.