10
\$\begingroup\$

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 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\$.

\$\endgroup\$
8
  • \$\begingroup\$ Sandbox. Brownie points to anyone who can beat my 6 bytes in Jelly. \$\endgroup\$ Oct 25 '20 at 17:08
  • \$\begingroup\$ Do the natural numbers start at 0 or 1? \$\endgroup\$
    – Lynn
    Oct 25 '20 at 17:12
  • \$\begingroup\$ @Lynn 1, you don't have to handle 0 \$\endgroup\$ Oct 25 '20 at 17:13
  • 3
    \$\begingroup\$ Just to verify: let \$S\$ be the set of all non-empty lists of natural numbers. My answer is a function \$S \to \mathbb N\$. But the task is not to write a bijection between \$S\$ and \$\mathbb N\$ here. Rather, for all \$n \geq 1\$, the restriction of my function to lists of length \$n\$ is bijective to \$\mathbb N\$. \$\endgroup\$
    – Lynn
    Oct 25 '20 at 17:28
  • 1
    \$\begingroup\$ @Lynn I really don't mind. Your answer must handle \$\mathbb{N} = \{1, 2, 3,\dots\}\$, but if you'd prefer to choose that \$\mathbb{N} = \{0, 1, 2, \dots\}\$ for your specific answer, I don't mind, so long as it's consistent for all \$n\$. I've edited this into the question for better visibility \$\endgroup\$ Oct 26 '20 at 23:25

14 Answers 14

6
\$\begingroup\$

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
\$\endgroup\$
5
\$\begingroup\$

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.

\$\endgroup\$
4
\$\begingroup\$

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
\$\endgroup\$
2
  • 1
    \$\begingroup\$ I used ð, but other than that, it's exactly my 6 byter \$\endgroup\$ Oct 25 '20 at 19:49
  • \$\begingroup\$ Very nice. I would be surprised if there was anything shorter for Jelly for this particular choice of pairing function. \$\endgroup\$
    – Sisyphus
    Oct 26 '20 at 0:43
4
\$\begingroup\$

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!

\$\endgroup\$
4
\$\begingroup\$

Charcoal, 21 18 bytes

W⊖Lθ⊞θ⊖×⊕⊗⊟θX²⊟θIθ

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

W⊖Lθ⊞θΣE²×⊕κ↨↨⊟貦⁴Iθ

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

W⊖Lθ

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

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

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.

Iθ

Output the final result.

\$\endgroup\$
7
  • \$\begingroup\$ FWIW porting this idea to Jelly gives a 10 - ;BUz0FUḄð/ - can you use a similar trick to golf this? (Repeatedly: Convert a & b to binarv; reverse them; zip them with filler 0; reverse; convert back from binary) \$\endgroup\$ Oct 25 '20 at 20:39
  • \$\begingroup\$ @JonathanAllan There's no Zip function in Charcoal, sadly. (But for Jelly, can you not do: Convert list to binary; reverse list elements; reduce by zip with filler; reverse; convert from binary; ?) \$\endgroup\$
    – Neil
    Oct 25 '20 at 21:06
  • \$\begingroup\$ Ah OK. Yes, with BU,z0Fɗ/UḄ unless I'm missing a golf. \$\endgroup\$ Oct 25 '20 at 21:34
  • \$\begingroup\$ @JonathanAllan Sisyphus points out that you can just zip the entire binary list in one go, but that's still 6 bytes. \$\endgroup\$
    – Neil
    Oct 26 '20 at 11:30
  • \$\begingroup\$ My comment was originally BUz0FUḄ for seven, but thought that was buggy so edited it to the ten-byter using reduction, but it's not buggy. So seven works, but six? \$\endgroup\$ Oct 26 '20 at 12:44
3
\$\begingroup\$

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
 ...                        ...
\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
3
  • 1
    \$\begingroup\$ My 6 byter also implements reducing by the Cantor function, you can remove a byte in the +’c2+ bit \$\endgroup\$ Oct 25 '20 at 17:54
  • 1
    \$\begingroup\$ Well, at least you didn't use the naïve +‘×+H+! \$\endgroup\$
    – Neil
    Oct 25 '20 at 18:39
  • \$\begingroup\$ @Neil That's how I was doing it at first too lol :P I still can't think of the 4-byte tho :( \$\endgroup\$
    – hyper-neutrino
    Oct 25 '20 at 18:51
2
\$\begingroup\$

JavaScript (ES6), 33 bytes

Cantor pairing on the input array a[].

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

Try it online!

\$\endgroup\$
2
\$\begingroup\$

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)
\$\endgroup\$
3
  • 1
    \$\begingroup\$ If you change the bijection slightly to add a instead of b, this can get to 9 bytes. Another 9-byter (left-reducing) is ćsvy+LOy+ \$\endgroup\$
    – ovs
    Oct 26 '20 at 23:58
  • \$\begingroup\$ I don't think this quite works. Consider \$n=1\$: 1 gets mapped to 2, 2 to 5 and there are no values that are mapped to 3 and 4 \$\endgroup\$
    – ovs
    Oct 27 '20 at 7:18
  • \$\begingroup\$ @ovs Ah, I missed the last rule "For every possible output, there exists an input which will give that output", I'll roll back to your 9-byter. Mb \$\endgroup\$ Oct 27 '20 at 8:12
1
\$\begingroup\$

Haskell, 31 bytes

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

Try it online!

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
0
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.