25
2
You should write a program or function which takes a non-negative integer N
as input and outputs or returns two integers (negative, zero or positive) X
and Y
.
Integers are meant in the mathematical sense as there are infinitely many of them.
The implemented function has to be bijective. This means that for every N
it has to output a different X
Y
pair and every X
Y
pair should be outputted for some input N
i.e. all of the following pairs should be outputted for some N
:
...
┌─────┬─────┬────┬────┬────┐
│-2 -2│-2 -1│-2 0│-2 1│-2 2│
├─────┼─────┼────┼────┼────┤
│-1 -2│-1 -1│-1 0│-1 1│-1 2│
├─────┼─────┼────┼────┼────┤
... │0 -2 │0 -1 │0 0 │0 1 │0 2 │ ...
├─────┼─────┼────┼────┼────┤
│1 -2 │1 -1 │1 0 │1 1 │1 2 │
├─────┼─────┼────┼────┼────┤
│2 -2 │2 -1 │2 0 │2 1 │2 2 │
└─────┴─────┴────┴────┴────┘
...
Note that U V
and V U
are different pairs if U!=V
.
Details
- If your language doesn't support arbitrarily large integers that's fine but your algorithm should work with an arbitrarily large integer data-type. Your code should still support input values for at least
2^31-1
. - If you choose to print or return the output as string no leading
0
's or+
signs are allowed. Otherwise your language's standard integer representation is fine.
Example
If the task would be to make a bijective function taking a non-negative integer N
and output one integer X
a solution could be the function
if (input mod 2 == 0) return N/2 else return -(N+1)/2
,
implemented in some language. This function returns X = 0 -1 1 -2 2...
for N = 0 1 2 3 4...
.
Can any of the integers in the output be repeated for different input? e. g.
10=>11 12, 9=>10 11
is this invalid because 11 is repeated? – BrainSteel – 2015-04-10T14:54:58.8471
As far as "bijective" is defined "11 12" not the same as "10 11" and therefore valid. This is because a bijective function is defined as a function "where every element of one set is paired with exactly one element of the other set, and every element of the other set is paired with exactly one element of the first set. There are no unpaired elements."(http://en.wikipedia.org/wiki/Bijection). If you were to inverse your function "11 12" should output 10 and "10 11" should output 9.
– GiantTree – 2015-04-10T15:05:13.780@BrainSteel Your example is valid. Only the (ordered) pairs can't be repeated. GiantTree is correct. Added some more explanation to the question. – randomra – 2015-04-10T15:08:11.490
Does it have to be a bijection within the integer range of the given language or should it work for all integers? – flawr – 2015-04-10T17:56:32.097
@flawr You can't do a bijection in a fixed range as the two sets will be of different size. Your algorithm should work for all integers using it on a proper datatype (see the first point of the Details section). – randomra – 2015-04-10T18:57:22.247
1@LegionMammal had a good mathematical description of the task: "You need to define a bijective function $f:N+→Z^2$. – LegionMammal978." that I think would be beneficial somewhere in the statement – Brian J – 2015-04-10T19:12:07.253
@BrianJ It was more like
$f:\mathbb{N}^+\rightarrow\mathbb{Z}^2$
= $f:\mathbb{N}^+\rightarrow\mathbb{Z}^2$. – LegionMammal978 – 2015-04-11T14:23:15.220@LegionMammal978 thanks! I couldn't see the markdown to copy directly. – Brian J – 2015-04-11T14:33:11.080