Bijective function ℤ → ℤⁿ

Question

It is trivially possible to create a bijective function from \$\mathbb{Z}\$ (the set of all integers) to \$\mathbb{Z}\$ (e.g. the identity function).

It is also possible to create a bijective function from \$\mathbb{Z}\$ to \$\mathbb{Z}^2\$ (the set of all pairs of 2 integers; the cartesian product of \$\mathbb{Z}\$ and \$\mathbb{Z}\$). For example, we could take the lattice representing integer points on a 2D plane, draw a spiral from 0 outwards, and then encode pairs of integers as the distance along the spiral when it intersects that point.

(A function which does this with natural numbers is known as a pairing function.)

In fact, there exists a family of these bijective functions:

$$f_k(x) : \mathbb{Z} \to \mathbb{Z}^k$$

The Challenge

Define a family of functions \$f_k(x)\$ (where \$k\$ is a positive integer) with the property that \$f_k(x)\$ bijectively maps integers to \$k\$-tuples of integers.

Your submission should, given inputs \$k\$ and \$x\$, return \$f_k(x)\$.

This is code-golf, so the shortest valid answer (measured in bytes) wins.

Specifications

• Any family \$f_k(x)\$ can be used as long as it fulfills the above criteria.
• You are encouraged to add a description of how your function family works, as well as a snippet to compute the inverse of the function (this is not included in your byte count).
• It is fine if the inverse function is uncomputable, as long as you can prove it the function is bijective.
• You can use any suitable representation for signed integers and lists of signed integers for your language, but you must allow inputs to your function to be unbounded.
• You only need to support values of \$k\$ up to 127.

Answer 1

Alice, 14 12 bytes

/O
\i@/t&Yd&

Try it online!

Inverse function (not golfed):

/o     Q
\i@/~~\ /dt&Z

Try it online!

Explanation

Alice has a built-in bijection between ℤ and ℤ², which can be computed with Y (unpack) and its inverse Z (pack). Here is an excerpt from the docs explaining the bijection:

The details of the bijection are likely irrelevant for most use cases. The main point is that it lets the user encode two integers in one and extract the two integers again later on. By applying the pack command repeatedly, entire lists or trees of integers can be stored in a single number (although not in a particularly memory-efficient way). The mapping computed by the pack operation is a bijective function ℤ² → ℤ (i.e. a one-to-one mapping). First, the integers {..., -2, -1, 0, 1, 2, ...} are mapped to the natural numbers (including zero) like {..., 3, 1, 0, 2, 4, ...} (in other words, negative integers are mapped to odd naturals and non-negative integers are mapped to even naturals). The two natural numbers are then mapped to one via the Cantor pairing function, which writes the naturals along the diagonals of the first quadrant of the integer grid. Specifically, {(0,0), (1,0), (0,1), (2,0), (1,1), (0,2), (3,0), ...} are mapped to {0, 1, 2, 3, 4, 5, 6, ...}. The resulting natural number is then mapped back to the integers using the inverse of the earlier bijection. The unpack command computes exactly the inverse of this mapping.

As alluded to above, we can use this unpack operation to map ℤ to ℤ^k as well. After applying it to the initial integer, we can unpack the second integer of the result again, which gives us a list of three integers. So k-1 applications of Y give us k integers as the result.

We can compute the inverse by packing the list up with Z from the end.

So the program itself has this structure:

/O
\i@/...d&

This is just a basic template for a program which reads a variable number of decimal integers as input and prints a variable number as the result. So the actual code is really just:

t   Decrement k.
&   Repeat the next command k-1 times.
Y   Unpack.

One thing I'd like to address is "why would Alice have a built-in for a ℤ → ℤ² bijection, isn't that golfing language territory"? As with most of Alice's weirder built-ins, the main reason is Alice's design principle that every command has two meanings, one for Cardinal (integer) mode and one for Ordinal (string) mode, and these two meanings should be somehow related to give Cardinal and Ordinal mode the feeling that they are mirror universes where things are sort of the same but also different. And quite often I had a command for one of the two modes I wanted to add, and then had to figure out what other command to pair it with.

In the case of Y and Z Ordinal mode came first: I wanted to have a function to interleave two strings (zip) and separate them again (unzip). The quality of this that I wanted to capture in Cardinal mode was to form one integer from two and be able to extract the two integers again later, which makes such a bijection the natural choice.

I also figured that this would actually be very useful outside of golfing, because it lets you store an entire list or even tree of integers in a single unit of memory (stack element, tape cell or grid cell).

Answer 2

Python, 96 93 bytes

def f(k,x):
 c=[0]*k;i=0
 while x:v=(x+1)%3-1;x=x//3+(v<0);c[i%k]+=v*3**(i//k);i+=1
 return c

This works in principle by converting the input number x to balanced ternary, and then distributing the trits (ternary digits) least-significant first between the different coordinates in a round-robin fashion. So for k=2 for example, every even positioned trit would contribute to the x coordinate, and every odd positioned trit would contribute to the y coordinate. For k=3 you'd have the first, fourth and seventh trits (etc...) contributing to x, while the second, fifth and eighth contribute to y, and the third, sixth and ninth contribute to z.

For example, with k=2, lets look at x=35. In balanced ternary, 35 is 110T (using the Wikipedia article's notation where T represents a -1 digit). Dividing the trits up gives 1T (the first and third trits, counting from the right) for the x coordinate and 10 (second and fourth trits) for the y coordinate. Converting each coordinate back to decimal, we get 2, 3.

Of course, I'm not actually converting the whole number to balanced ternary at once in the golfed code. I'm just computing one trit at a time (in the v variable), and adding its value directly to the appropriate coordinate.

Here's an ungolfed inverse function that takes a list of coordinates and returns a number:

def inverse_f(coords):
    x = 0
    i = 0
    while any(coords):
        v = (coords[i%3]+1) % 3 - 1
        coords[i%3] = coords[i%3] // 3 + (v==-1)
        x += v * 3**i
        i += 1
    return x

My f function is perhaps notable for its performance. It uses only O(k) memory and takes O(k) + O(log(x)) time to find the results, so it can work with very large input values. Try f(10000, 10**10000) for instance, and you'll get an answer pretty much instantly (adding an extra zero to the exponent so x is 10**100000 makes it take 30 seconds or so on my old PC). The inverse function is not as fast, mostly because it's hard for it to tell when it's done (it scans all the coordinates after each change, so it takes something like O(k*log(x)) time). It could probably be optimized to be faster, but it's probably fast enough for normal parameters already.

Answer 3

Husk, 10 bytes

§~!oΠR€Θݱ

Try it online!

The inverse function is also 10 bytes.

§o!ȯ€ΠRΘݱ

Try it online!

Explanation

Forward direction:

§~!oΠR€Θݱ  Implicit inputs, say k=3 and x=-48
        ݱ  The infinite list [1,-1,2,-2,3,-3,4,-4,..
       Θ    Prepend 0: [0,1,-1,2,-2,3,-3,4,-4,..
 ~    €     Index of x in this sequence: 97
§    R      Repeat the sequence k times: [[0,1,-1,..],[0,1,-1,..],[0,1,-1,..]]
   oΠ       Cartesian product: [[0,0,0],[1,0,0],[0,1,0],[1,1,0],[-1,0,0],[0,0,1],..
  !         Index into this list using the index computed from x: [-6,1,0]

Reverse direction:

§o!ȯ€ΠRΘݱ  Implicit inputs, say k=3 and y=[-6,1,0]
     ΠRΘݱ  As above, k-wise Cartesian product of [0,1,-1,2,-2,..
   ȯ€       Index of y in this sequence: 97
§o!         Index into the sequence [0,1,-1,2,-2,.. : -48

The Cartesian product built-in Π behaves nicely for infinite lists, enumerating each k-tuple exactly once.

Answer 4

Wolfram Language (Mathematica), 61 bytes

SortBy[Range[-(x=2Abs@#+Boole[#>=0]),x]~Tuples~#2,#.#&][[x]]&

Try it online!

(Takes the integer and then the length of the tuple as input.)

Inverse:

If[OddQ[#],#-1,-#]/2&@Tr@Position[SortBy[Range[-(x=Ceiling@Norm@#),x]~Tuples~Length@#,#.#&],#]&

Try it online!

How it works

The idea is straightforward: we turn the integer input into a positive integer (by mapping 0,1,2,3,... to 1,3,5,7,... and -1,-2,-3,... to 2,4,6,...) and then index into all the k-tuples, sorted by distance from the origin and then by Mathematica's default tie-breaking.

But we can't use an infinite list, so when we're looking for the n^th k-tuple, we only generate k-tuples of integers in the range {-n,...,n}. This is guaranteed to be enough, because the n^th smallest k-tuple by norm has norm less than n, and all tuples of norm n or less are included in this list.

For the inverse, we just generate a long enough list of k-tuples, find the position of the given k-tuple in that list, and then invert the "fold into a positive integer" operation.

Answer 5

J, 7 Bytes

#.,|:#:

The J code to do this embarrassingly simple

A very simple pairing function (or, tupling function) is to simply interleave the digits of the binary expansion of each of the numbers. So, for instance (47, 79) would be paired as such:

1_0_0_1_1_1_1
 1_0_1_1_1_1
-------------
1100011111111

or, 6399. Obviously, we can trivially generalize to any n-tuple.

Let's examine how this works verb by verb.

#: is anti-base two, when used monadically it returns the binary expansion of a number. #: 47 79 gives the result:

0 1 0 1 1 1 1
1 0 0 1 1 1 1

|: is the transpose operator, which simply rotates an array. Rotating the result of #: 47 79 gives:

0 1
1 0
0 0
1 1
1 1
1 1
1 1

When used monadically, , is the ravel operator, it produces a 1-dimensional list from an table:

0 1 1 0 0 0 1 1 1 1 1 1 1 1

Finally, #. converts the binary expansion back, giving us the result 6339.

This solution will work for any string of integers.

Answer 6

Perl 6, 148 bytes

my@s=map ->\n{|grep {n==abs any |$_},(-n..n X -n..n)},^Inf;my&f={$_==1??+*!!do {my&g=f $_-1;my@v=map {.[0],|g .[1]},@s;->\n{@v[n>=0??2*n!!-1-2*n]}}}

Try it online!

Ungolfed:

sub rect($n) {
    grep ->[$x,$y] { abs($x|$y) == $n }, (-$n..$n X -$n..$n);
}

my @spiral = map { |rect($_) }, ^Inf;

sub f($k) {
    if ($k == 1) {
        -> $_ { $_ }
    } else {
        my &g = f($k-1);
        my @v = map -> [$x, $y] { $x, |g($y) }, @spiral;
        -> $_ { $_ >= 0 ?? @v[2*$_] !! @v[-1-2*$_] }
    }
}

Explanation:

• rect($n) is a helper function that generates the coordinates of the integral points on the edge of a rectangle from coordinates (-$n,$n) to ($n, $n).

• @spiral is a lazy, infinite list of the integral points on the edges of rectangles of increasing size, starting from 0.

• f($k) returns a function which is a bijection from the integers to $k-tuples of integers.

If $k is 1, f returns the identity mapping -> $_ { $_ }.

Otherwise, &g is the recursively obtained mapping from the integers to $k-1-tuples of integers.

Then, we @spiral out from the origin, and at each point form a $k-tuple by taking the X-coordinate and the flattened result of calling g with the Y-coordinate. This lazily generated mapping is stored in the array @v.

@v contains all $k-tuples starting with index 0, so to extend the indexing to the negative integers, we just map positive inputs to the even numbers and negative inputs to the odd numbers. A function (closure) is returned which looks up elements of @v in this way.

Answer 7

JavaScript, 155 bytes

f=k=>x=>(t=x<0?1+2*~x:2*x,h=y=>(g=(v,p=[])=>1/p[k-1]?v||t--?0:p.map(v=>v&1?~(v/2):v/2):[...Array(1+v)].map((_,i)=>g(v-i,[...p,i])).find(u=>u))(y)||h(y+1))(0)

f=k=>x=>(t=x<0?1+2*~x:2*x,h=y=>(g=(v,p=[])=>1/p[k-1]?v||t--?0:p.map(v=>v&1?~(v/2):v/2):[...Array(1+v)].map((_,i)=>g(v-i,[...p,i])).find(u=>u))(y)||h(y+1))(0)

<p>k = <input id=k value=2>
<p>from <input id=a value=-5>
<p>to <input id=b value=5>
<p><button type="button" onclick="for(o.value='',i=+a.value;i<=b.value;i++)o.value+=[i,f(+k.value)(i)].join(':')+'\n';">generate</button>
<p><pre><output id=o>

Prettify version:

k => x => {
  // Map input to non-negative integer
  if (x > 0) t = 2 * x; else t = 2 * -x - 1;
  // we try to generate all triples with sum of v
  g = (v, p = []) => {
    if (p.length === k) {
      if (v) return null;
      if (t--) return null;
      // if this is the t-th one we generate then we got it
      return p;
    }
    for (var i = 0; i <= v; i++) {
      var r = g(v-i, [...p, i]);
      if (r) return r;
    }
  }
  // try sum from 0 to infinity
  h = x => g(x) || h(x + 1);
  // map tuple of non-negative integers back
  return h(0).map(v => {
    if (v % 2) return -(v + 1) / 2
    else return v / 2;
  });
}

• First, we map all integers to all non-negative integers one by one:
  • if n > 0 then result = n * 2
  • otherwise result = -n * 2 - 1
• Second, we give all tuples with k-length non-negative integers an order:
  • calculate sum of all element, smaller one comes first
  • if sum is equal, compare from left to right, smaller one comes first
  • As a result, we got the map for all non-negative integers to tuples with k non-negative integers
• Finally, map non-negative integers in tuple given in second step to all integers with similar formula in first step

Answer 8

Wolfram Language (Mathematica), 107 bytes

(-1)^#⌈#/2⌉&@Nest[{w=⌊(√(8#+1)-1)/2⌋;x=#-w(w+1)/2,w-x}~Join~{##2}&@@#&,{2Abs@#-Boole[#<0]},#2-1]&

Try it online!

Inverse, 60 bytes

(-1)^#⌈#/2⌉&@Fold[+##(1+##)/2+#&,2Abs@#-Boole[#<0]&/@#]&

Try it online!

Explanation:

Z -> N0 via f(n) = 2n if n>=0 and -2n-1 if n<0

N0 -> N0^2 via inverse of the pairing function

N0 -> N0^k Repeatedly apply the above to the leftmost number until we get length k

N0^k -> Z^k via f(n) = (-1)^n * ceil(n/2), element-wise

---

Mathematica, 101 bytes

(-1)^#⌈#/2⌉&@Nest[{a=#~IntegerExponent~2+1,#/2^a+1/2}~Join~{##2}&@@#&,{2Abs@#+Boole[#<=0]},#2-1]&

Similar to above (uses N instead of N0), but uses the inverse of the bijection f: N^2 -> N via f(a, b) = 2^(a - 1)(2b - 1)

Answer 9

JavaScript, 112 bytes

k=>x=>(r=Array(k).fill(''),[...`${x<0?2*~x+1:2*x}`].map((c,i,s)=>r[(s.length-i)%k]+=c),r.map(v=>v&1?~(v/2):v/2))

1. convert to non-negative
2. (n*k+i)th digit to i-th number
3. convert back

Answer 10

05AB1E, 20 bytes

[D_#>3‰`<s])sô0ζεR3β

Try it online! Port of @Blckknght's answer. Inverse, 17 bytes:

[Z_#>3‰ø`<s])˜R3β

Try it online!

Answer 11

Jelly, 15 bytes

µ<1ạḤðŒRṗAS$Þ⁸ị

Try it online!

1-indexed.

Inverse:

AṀ×LŒRṗLAS$Þiµ:2NḂ}¡

Try it online!