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

Question

Il tuo compito è scrivere un programma che implementa una biiezione \$\mathbb{N}^n\to\mathbb{N}\$per \$n \ge 1\$. Il tuo programma dovrebbe richiedere \$n\$numeri naturali come input, in qualsiasi metodo accettabile (incluso prenderli come un unico, \$n\$ elenco / array di elementi) e restituisce un numero naturale univoco per tutti i possibili input.

In parole povere , una biiezione \$\mathbb{N}^n\to\mathbb{N}\$ si intende:

• Prendi \$n\$ numeri naturali come input
• Mappa questi \$n\$ numeri naturali in un singolo output di numeri naturali
• Per ogni possibile input, l'output è decisamente unico
• Per ogni possibile output, esiste un input che darà quell'output

Ad esempio, la funzione di associazione di Cantor \$\pi : \mathbb{N}^2\to\mathbb{N}\$ è una biiezione che prende due numeri naturali e mappa ogni coppia su un numero naturale univoco.

Puoi implementare qualunque funzione biiettiva desideri, purché sia ​​dimostrato di essere biiettiva per tutti i possibili input. Si prega di includere questa prova (direttamente o tramite un collegamento) nella risposta. Questo è il codice del golf, quindi il codice più breve, in byte, vince.

Puoi decidere se desideri utilizzare \$\mathbb{N} = \{1, 2, 3, \dots\}\$o \$\mathbb{N} = \{0, 1, 2, \dots\}\$, a condizione che sia coerente per tutti \$n\$.

Answer 1

APL (Dyalog Unicode) , 13 10 byte

(⊢+1⊥∘⍳+)/

Provalo online!

Simile ad altre risposte, poiché l'abbinamento di Cantor è biettivo, il compositing \$n-1\$ Anche gli abbinamenti di Cantor sono biettivi.

(       )/  ⍝ 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 byte

,@|:&.#:

Provalo online! (restituisce la matrice 10x10 per f (A, B) e alcuni numeri consecutivi per n = 3.)

Fondamentalmente utilizza l'idea iniziale di Neil, intrecciando i bit distribuendoli uniformemente (quindi per n = 3, la maschera di bit per l'output è … 1 2 3 1 2 3 1 2 3.). Ma invece di spostare i bit, utilizziamo le forme: converti ogni numero in base 2 e gli elenchi dei pad con zeri, fe #: 2 3 8è

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

Trasponi la matrice con |::

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

E 'deshape' con ,, cioè unisci le righe in un elenco: 0 0 1 0 0 0 1 1 0 0 1 0e riconvertilo dalla base 2 &.#:in un numero: 562.

Answer 3

Gelatina , 6 byte

Probabilmente il 6 byter di Caird ...

+RS+ʋ/

Provalo online!

Come?

Implementa un'applicazione ripetuta della funzione di associazione di Cantor.

Una singola applicazione è \$f(a,b)=\frac{1}{2}(a+b)(a+b+1)+b\$

Ma nota che \$\frac{1}{2}(a+b)(a+b+1)=\sum_{i=1}^{a+b}i\$

Quindi \$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 byte

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

Provalo online!

Accetta input in modo splattato f(1,2,3).

Utilizza la funzione di associazione \$p(a,b)=(2a+1)2^b\$. Usiamo bit-shift <<bper accorciare *2**be scrivere a-~aper salvare un byte da 2*a+1.

41 byte

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

Provalo online!

Answer 5

Carboncino , 21 18 byte

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

Provalo online! Ora usa la funzione di accoppiamento di @ xnor. Risposta precedente a 21 byte:

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

Provalo online! Il collegamento è alla versione dettagliata del codice. Spiegazione:

Ｗ⊖Ｌθ

Ripeti finché non rimane un solo elemento (cioè riduci a destra) ...

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

Converti gli ultimi due elementi in base 2 e poi torna dalla base 4, raddoppia uno di essi e prendi la somma, riportando il risultato nell'elenco. Ciò equivale a intercalare i loro bit. Uso questa biiezione piuttosto che la funzione di accoppiamento Cantor poiché richiede solo la lettura di ogni valore una volta, rendendolo così più golfista in Charcoal.

Ｉθ

Stampa il risultato finale.

Answer 6

Haskell , 27 byte

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

Provalo online!

Utilizza una biiezione diversa dalla funzione di associazione di Cantor. Ogni numero intero positivo può essere suddiviso in modo univoco in una potenza di 2 volte un numero dispari, ovvero \$2^a(2b+1)\$per numeri interi non negativi \$a,b\$. Sottraendo 1 quindi significa che otteniamo tutti i numeri interi non negativi incluso 0.

Ecco una tabella per la biiezione, per \$a,b\$ da 0 a 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

Gelatina , 7 byte

+‘c2+µ/

Provalo online!

0 è un numero naturale.

Implementa l'accoppiamento Cantor e riduce l'elenco oltre quello.

(A quanto pare c'è una soluzione a 6 byte quindi sono triste)

L'abbinamento di Cantor è biettivo (non sono sicuro della prova ma credo sia ben noto), quindi poiché le composizioni di biiezioni sono biiettive, questo è biettivo. Nel caso limite che n = 1, questa è identità, quindi è ancora biiettiva.

Almeno, è così che penso che funzioni. Per favore fatemi sapere se trovate un valore non mappato o una collisione.

Answer 8

JavaScript (ES6), 33 byte

Associazione Cantor sull'array di input a[].

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

Provalo online!

Answer 9

05AB1E , 10 9 byte

Å«+LOy+}н

Provalo online o verifica tutti i casi di test .

Port of @ovs 'APL answer , quindi assicurati di votare a favore!
-1 byte grazie a @ovs .

Alternativa a 9 byte :

ćsvy+LOy+

Provalo online o verifica altri casi di test .

Spiegazione:

Å«         # 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 byte

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

Provalo online!

Answer 11

Scala, 34 byte

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

Provalo online

Una funzione anonima di tipo Seq[Int] => Int. Applica l'accoppiamento cantore a due elementi finché il risultato è un unico intero.

Answer 12

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

Ho salvato un byte grazie a Ceilingcat !!!

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

Provalo online!

Inserisce un array di numeri naturali e la sua lunghezza meno \$1\$e restituisce un numero naturale univoco utilizzando l' associazione Cantor .

Answer 13

Husk , 7 byte

FS+ȯΣḣ+

Provalo online!

Accoppiamento di Cantore ricorsivo (stesso approccio della risposta di HyperNeutrino ).

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 byte

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

_
@_
+`_@
@__
_

Provalo online! Spiegazione:

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

Converti l'input in binario, usando @for 0e _for 1.

^'@P`.+

Tasto sinistro su tutte le linee con @la stessa lunghezza.

N$`. $.%`
¶

Trasponi e unisci le linee.

_
@_
+`_@
@__
_

Converti da binario a decimale.