Golf eine Bijektion \ $\mathbb{N}^n\to\mathbb{N}\$
Ihre Aufgabe ist es, ein Programm zu schreiben , die eine Bijektion implementiert \$\mathbb{N}^n\to\mathbb{N}\$für \$n \ge 1\$. Ihr Programm sollte \ nehmen$n\$natürliche Zahlen als Eingabe in jeder akzeptablen Methode (einschließlich der Aufnahme als einzelne, \$n\$ Elementliste / Array) und geben eine eindeutige natürliche Zahl für alle möglichen Eingaben aus.
In juristischer Hinsicht, eine Bijektion \$\mathbb{N}^n\to\mathbb{N}\$ meint:
- Nimm \$n\$ natürliche Zahlen als Eingabe
- Karte dieser \$n\$ natürliche Zahlen zu einer einzelnen natürlichen Zahlenausgabe
- Für jede mögliche Eingabe ist die Ausgabe nachweislich eindeutig
- Für jede mögliche Ausgabe gibt es eine Eingabe, die diese Ausgabe liefert
Zum Beispiel die Cantor-Pairing-Funktion \$\pi : \mathbb{N}^2\to\mathbb{N}\$ ist eine Bijektion, die zwei natürliche Zahlen verwendet und jedes Paar einer eindeutigen natürlichen Zahl zuordnet.
Sie können jede gewünschte bijektive Funktion implementieren, sofern sich herausstellt, dass sie für alle möglichen Eingaben bijektiv ist. Bitte fügen Sie diesen Beweis (entweder direkt oder über einen Link) in Ihre Antwort ein. Dies ist Code-Golf, also gewinnt der kürzeste Code in Bytes.
Sie können entscheiden, ob Sie \ verwenden möchten$\mathbb{N} = \{1, 2, 3, \dots\}\$oder \$\mathbb{N} = \{0, 1, 2, \dots\}\$, solange dies für alle konsistent ist \$n\$.
Antworten
APL (Dyalog Unicode) , 13 10 Bytes
(⊢+1⊥∘⍳+)/
Probieren Sie es online aus!
Ähnlich wie bei anderen Antworten, da die Cantor - Paarung bijektiv ist, Compositing \$n-1\$ Cantor-Paarungen sind ebenfalls bijektiv.
( )/ ⍝ 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
J , 8 Bytes
,@|:&.#:
Probieren Sie es online aus! (Gibt die 10x10-Matrix für f (A, B) und einige fortlaufende Zahlen für n = 3 aus.)
Grundsätzlich wird Neils ursprüngliche Idee verwendet, die Bits durch gleichmäßige Verteilung miteinander zu verweben (für n = 3 lautet die Bitmaske für die Ausgabe … 1 2 3 1 2 3 1 2 3). Aber anstatt die Bits zu verschieben, verwenden wir Formen: Konvertieren Sie jede Zahl in Basis 2 und Pad-Listen mit Nullen, z. B. #: 2 3 8ist
0 0 1 0
0 0 1 1
1 0 0 0
Transponieren Sie die Matrix mit |::
0 0 1
0 0 0
1 1 0
0 1 0
Und 'entformen' mit ,, dh verbinden Sie die Zeilen zu einer Liste: 0 0 1 0 0 0 1 1 0 0 1 0und konvertieren Sie sie von Basis 2 zurück &.#:in eine Zahl: 562.
Gelee , 6 Bytes
Wahrscheinlich Cairds 6 Byter ...
+RS+ʋ/
Probieren Sie es online aus!
Wie?
Implementiert eine wiederholte Anwendung der Cantor-Pairing-Funktion.
Eine einzelne Anwendung ist \$f(a,b)=\frac{1}{2}(a+b)(a+b+1)+b\$
Beachten Sie jedoch, dass \$\frac{1}{2}(a+b)(a+b+1)=\sum_{i=1}^{a+b}i\$
Also \$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
Python 2 , 38 Bytes
f=lambda a,*l:l and(a-~a<<f(*l))-1or a
Probieren Sie es online aus!
Nimmt die Eingabe wie bespritzt auf f(1,2,3).
Verwendet die Pairing-Funktion \$p(a,b)=(2a+1)2^b\$. Wir verwenden Bit-Shift <<b, um zu verkürzen *2**b, und schreiben a-~a, um ein Byte zu sparen 2*a+1.
41 Bytes
lambda l:reduce(lambda a,b:(a-~a<<b)-1,l)
Probieren Sie es online aus!
Holzkohle , 21 18 Bytes
Ｗ⊖Ｌθ⊞θ⊖×⊕⊗⊟θＸ²⊟θＩθ
Probieren Sie es online aus! Verwendet jetzt die Pairing-Funktion von @ xnor. Vorherige 21-Byte-Antwort:
Ｗ⊖Ｌθ⊞θΣＥ²×⊕κ↨↨⊟貦⁴Ｉθ
Probieren Sie es online aus! Der Link führt zur ausführlichen Version des Codes. Erläuterung:
Ｗ⊖Ｌθ
Wiederholen, bis nur noch ein Element übrig ist (dh rechts reduzieren) ...
⊞θΣＥ²×⊕κ↨↨⊟貦⁴
Konvertieren Sie die letzten beiden Elemente in Basis 2 und dann zurück von Basis 4, verdoppeln Sie eines davon und nehmen Sie die Summe, um das Ergebnis zurück in die Liste zu verschieben. Dies entspricht der Verschachtelung ihrer Bits. Ich verwende diese Bijektion anstelle der Cantor-Pairing-Funktion, da jeder Wert nur einmal gelesen werden muss, wodurch er in Charcoal Golf spielt.
Ｉθ
Geben Sie das Endergebnis aus.
Haskell , 27 Bytes
foldr1(\a b->2^a*(2*b+1)-1)
Probieren Sie es online aus!
Verwendet eine andere Bijektion als die Cantor-Pairing-Funktion. Jede positive ganze Zahl kann eindeutig in eine Zweierpotenz einer ungeraden Zahl aufgeteilt werden, dh \$2^a(2b+1)\$für nicht negative ganze Zahlen \$a,b\$. Das Subtrahieren von 1 bedeutet dann, dass wir alle nicht negativen ganzen Zahlen einschließlich 0 erhalten.
Hier ist eine Tabelle für die Bijektion für \$a,b\$ von 0 bis 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
... ...
Gelee , 7 Bytes
+‘c2+µ/
Probieren Sie es online aus!
0 ist eine natürliche Zahl.
Implementiert Cantor Pairing und reduziert die Liste darüber hinaus.
(Es gibt anscheinend eine 6-Byte-Lösung, also bin ich traurig)
Cantor Pairing ist bijektiv (ich bin mir des Beweises nicht sicher, aber das ist meiner Meinung nach bekannt). Da Kompositionen von Bijektionen bijektiv sind, ist dies bijektiv. In dem Randfall, dass n = 1 ist, ist dies Identität, also immer noch bijektiv.
Zumindest denke ich, dass das so funktioniert. Bitte lassen Sie mich wissen, wenn Sie einen nicht zugeordneten Wert oder eine Kollision finden.
JavaScript (ES6), 33 Byte
Cantor-Pairing auf dem Eingabearray a[].
a=>a.reduce((x,y)=>y-(x+=y)*~x/2)
Probieren Sie es online aus!
05AB1E , 10 9 Bytes
Å«+LOy+}н
Probieren Sie es online aus oder überprüfen Sie alle Testfälle .
Port of @ovs 'APL-Antwort , also stellen Sie sicher, dass Sie ihn positiv bewerten!
-1 Byte dank @ovs .
9 Bytes Alternative:
ćsvy+LOy+
Probieren Sie es online aus oder überprüfen Sie weitere Testfälle .
Erläuterung:
Å« # 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)
Haskell, 31 Bytes
foldl1(\x y->(x+y)*(x+y+1)/2+y)
Probieren Sie es online aus!
Scala, 34 Bytes
_.reduce((x,y)=>(x+y)*(x+y+1)/2+y)
Probieren Sie es online aus
Eine anonyme Funktion vom Typ Seq[Int] => Int. Wendet die Cantor-Paarung auf zwei Elemente an, bis das Ergebnis eine einzelne Ganzzahl ist.
C (gcc) , 62 \$\cdots\$ 56 55 Bytes
Dank Deckenkatze ein Byte gespart !!!
f(a,l)int*a;{l=l?*++a=*a-(*a+=a[1])*~*a/2,f(a,l-1):*a;}
Probieren Sie es online aus!
Gibt ein Array natürlicher Zahlen und deren Länge minus \ ein$1\$und gibt mithilfe der Cantor-Paarung eine eindeutige natürliche Zahl zurück .
Schale , 7 Bytes
FS+ȯΣḣ+
Probieren Sie es online aus!
Rekursive Cantor-Paarung (gleicher Ansatz wie die Antwort von 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
Netzhaut , 59 Bytes
.+
*
+`(_+)\1
$1@ @_ _ ^'@P`.+ N$`.
$.%`
¶
_
@_
+`_@
@__
_
Probieren Sie es online aus! Erläuterung:
.+
*
+`(_+)\1
$1@
@_
_
Konvertieren Sie die Eingabe mit @for 0und _for in binär 1.
^'@P`.+
Füllen Sie alle Zeilen mit @der gleichen Länge nach links .
N$`. $.%`
¶
Transponieren und verbinden Sie die Linien.
_
@_
+`_@
@__
_
Konvertieren Sie von binär in dezimal.