1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

I Symmetric injective mapping from N² to N

  1. Mar 1, 2016 #1
    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
     
  2. jcsd
  3. Mar 1, 2016 #2

    jbriggs444

    User Avatar
    Science Advisor

    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.
     
  4. Mar 1, 2016 #3

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    One idea is to map to a subset of N with integers composed of just the digits 1 and 2, for example.
     
  5. Mar 1, 2016 #4
    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.
     
  6. Mar 1, 2016 #5

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Well, you posted under Maths not computer science. Mapping a finite set is trivial.
     
  7. Mar 1, 2016 #6

    jbriggs444

    User Avatar
    Science Advisor

    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:

    Code (Text):

    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.
     
  8. Mar 1, 2016 #7
    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.

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

    which yields
    [tex]
    x_n = \frac{n^2 + n}{2}
    [/tex]

    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:
    [tex]
    x(r, c) = \frac{r^2 + r}{2} + c
    [/tex]
    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:
    [tex]
    9223372036854775807 = \frac{max^2 + max}{2} + max
    [/tex]
    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).
     
    Last edited: Mar 1, 2016
  9. Mar 1, 2016 #8

    jbriggs444

    User Avatar
    Science Advisor

    Yep. That is what I had in mind.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Symmetric injective mapping from N² to N
  1. N /n! = ? (Replies: 21)

Loading...