Golf a bijection \$\mathbb{N}^n\to\mathbb{N}\$

Question

Your task is to write a program which implements a bijection \$\mathbb{N}^n\to\mathbb{N}\$ for \$n \ge 1\$. Your program should take \$n\$ natural numbers as input, in any acceptable method (including taking them as a single, \$n\$ element list/array) and output a unique natural number for all possible inputs.

In layman's terms, a bijection \$\mathbb{N}^n\to\mathbb{N}\$ means:

• Take \$n\$ natural numbers as input
• Map these \$n\$ natural numbers to a single natural number output
• For every possible input, the output is provably unique
• For every possible output, there exists an input which will give that output

For example, the Cantor pairing function \$\pi : \mathbb{N}^2\to\mathbb{N}\$ is a bijection that takes two natural numbers and maps each pair to a unique natural number.

You may implement whatever bijective function you wish, so long as it is proven to be bijective for all possible inputs. Please include this proof (either directly or through a link) in your answer. This is code-golf so the shortest code, in bytes, wins.

You may decide whether you'd like to use \$\mathbb{N} = \{1, 2, 3, \dots\}\$ or \$\mathbb{N} = \{0, 1, 2, \dots\}\$, so long as this is consistent for all \$n\$.

Answer 1

APL (Dyalog Unicode), 13 10 bytes

(⊢+1⊥∘⍳+)/

Try it online!

Similar to other answers, since the Cantor pairing is bijective, compositing \$n-1\$ Cantor pairings is bijective as well.

(       )/  ⍝ reduce the input with following function
       +    ⍝ left argument + right argument
      ⍳     ⍝ the first left+right positive integers
   1⊥       ⍝ convert those from base 1 (sum)
 ⊢+         ⍝ + right argument

Answer 2

J, 8 bytes

,@|:&.#:

Try it online! (outputs the 10x10 matrix for f(A,B) and some consecutive numbers for n=3.)

Basically uses Neil's initial idea, interweaving the bits by evenly distributing them (so for n=3, the bit mask for the output is … 1 2 3 1 2 3 1 2 3.). But instead of shifting the bits, we make use of shapes: Convert each number into base 2 and pad lists with zeros, f.e. #: 2 3 8 is

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

Transpose the matrix with |::

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

And 'deshape' with ,, i.e. join the rows into a list: 0 0 1 0 0 0 1 1 0 0 1 0 and convert it back from base 2 &.#: into a number: 562.

Answer 3

Jelly, 6 bytes

Probably caird's 6 byter...

+RS+ʋ/

Try it online!

How?

Implements a repeated application of the Cantor pairing function.

A single application is \$f(a,b)=\frac{1}{2}(a+b)(a+b+1)+b\$

But note that \$\frac{1}{2}(a+b)(a+b+1)=\sum_{i=1}^{a+b}i\$

So \$f(a,b)=b+\sum_{i=1}^{a+b}i\$

+RS+ʋ/ - Link: list of non-negative integers
     / - reduce by:
    ʋ  -   last four links as a dyad - f(a,b)
+      -     add     -> a+b
 R     -     range   -> [1,2,3,...,a+b]
  S    -     sum     -> (a+b)(a+b+1)/2
   +   -     add (b) -> b+(a+b)(a+b+1)/2

Answer 4

Python 2, 38 bytes

f=lambda a,*l:l and(a-~a<<f(*l))-1or a

Try it online!

Takes input splatted like f(1,2,3).

Uses the pairing function \$p(a,b)=(2a+1)2^b\$. We use bit-shift <<b to shorten *2**b, and write a-~a to save a byte off of 2*a+1.

41 bytes

lambda l:reduce(lambda a,b:(a-~a<<b)-1,l)

Try it online!

Answer 5

Charcoal, 21 18 bytes

Ｗ⊖Ｌθ⊞θ⊖×⊕⊗⊟θＸ²⊟θＩθ

Try it online! Now uses @xnor's pairing function. Previous 21-byte answer:

Ｗ⊖Ｌθ⊞θΣＥ²×⊕κ↨↨⊟貦⁴Ｉθ

Try it online! Link is to verbose version of code. Explanation:

Ｗ⊖Ｌθ

Repeat until there is only one element left (i.e. reduce right)...

⊞θΣＥ²×⊕κ↨↨⊟貦⁴

Convert the last two elements to base 2 and then back from base 4, double one of them and take the sum, pushing the result back to the list. This is equivalent to interleaving their bits. I use this bijection rather than the Cantor pairing function as it only requires reading each value once, thus making it golfier in Charcoal.

Ｉθ

Output the final result.

Answer 6

Haskell, 27 bytes

foldr1(\a b->2^a*(2*b+1)-1)

Try it online!

Uses a different bijection from the Cantor pairing function. Every positive integer can be uniquely split into a power of 2 times an odd number, that is \$2^a(2b+1)\$ for non-negative integers \$a,b\$. Subtracting 1 then means we get all non-negative integers including 0.

Here's a table for the bijection, for \$a,b\$ from 0 to 6:

  0   2   4   6   8  10  12 ...
  1   5   9  13  17  21  25
  3  11  19  27  35  43  51
  7  23  39  55  71  87 103
 15  47  79 111 143 175 207
 31  95 159 223 287 351 415
 63 191 319 447 575 703 831
 ...                        ...

Answer 7

Jelly, 7 bytes

+‘c2+µ/

Try it online!

0 is a natural number.

Implements Cantor Pairing, and reduces the list over that.

(There's a 6 byte solution apparently so I'm sad)

Cantor Pairing is bijective (I'm not sure of the proof but this is well known I think), so since compositions of bijections are bijective, this is bijective. In the edge case that n = 1, this is identity, so it's still bijective.

At least, that's how I think that works. Please let me know if you find an unmapped value or a collision.

Answer 8

JavaScript (ES6), 33 bytes

Cantor pairing on the input array a[].

a=>a.reduce((x,y)=>y-(x+=y)*~x/2)

Try it online!

Answer 9

05AB1E, 10 9 bytes

Å«+LOy+}н

Try it online or verify all test cases.

Port of @ovs' APL answer, so make sure to upvote him!
-1 byte thanks to @ovs.

9 bytes alternative:

ćsvy+LOy+

Try it online or verify some more test cases.

Explanation:

Å«         # Cumulative right-reduce by (unfortunately keeping all intermediate steps):
  +        #  Add them together: a+b
   L       #  Pop and push a list in the range [a+b]
    O      #  Sum this list
     y+    #  Add a to it
 }н        # After the reduce-by, pop the list and leave just the first item
           # (after which it is output implicitly as result)

ć          # Extract head of the (implicit) input-list; pushing the remainder-list
           # and first item separated to the stack
 s         # Swap so the remainder-list is at the top
  v        # Loop over each integer `y` in this list:
   y+      #  Add the current integer `y` to the top value
     L     #  Pop and push a list in the range [1,n]
      O    #  Sum this list
       y+  #  And add `y` to it
           # (after the loop, the integer is output implicitly as result)

Answer 10

Haskell, 31 bytes

foldl1(\x y->(x+y)*(x+y+1)/2+y)

Try it online!

Answer 11

Scala, 34 bytes

_.reduce((x,y)=>(x+y)*(x+y+1)/2+y)

Try it online

An anonymous function of type Seq[Int] => Int. Applies the cantor pairing to two elements until the result is an a single integer.

Answer 12

C (gcc), ^{62 \$\cdots\$ 56} 55 bytes

Saved a byte thanks to ceilingcat!!!

f(a,l)int*a;{l=l?*++a=*a-(*a+=a[1])*~*a/2,f(a,l-1):*a;}

Try it online!

Inputs an array of natural numbers and its length minus \$1\$ and returns a unique natural number using Cantor pairing.

Answer 13

Husk, 7 bytes

FS+ȯΣḣ+

Try it online!

Recursive Cantor pairing (same approach as HyperNeutrino's answer).

FS+ȯΣḣ+
F           # Fold over list (=recursively apply to pairs):
 S+ȯΣḣ+     # Cantor-pairing bijection:
 S          # Hook: combine 2 functions using same (first) argument
  +         # add first argument to
   ȯ        # combination of 2 3 functions:
    Σ       # sum of
     ḣ      # series from 1 up to
      +     # sum of first & second arguments

Answer 14

Retina, 59 bytes

.+
*
+`(_+)\1
$1@
@_
_
^'@P`.+
N$`.
$.%`
¶

_
@_
+`_@
@__
_

Try it online! Explanation:

.+
*
+`(_+)\1
$1@
@_
_

Convert the input to binary, using @ for 0 and _ for 1.

^'@P`.+

Left-pad all lines with @ to the same length.

N$`.
$.%`
¶

Transpose and join the lines.

_
@_
+`_@
@__
_

Convert from binary to decimal.